Baez’s “42” – Solving the first puzzle

In a blog post, John Baez proposes the following puzzle:

Consider solutions of

\displaystyle \frac{1}{p} + \frac{1}{q} + \frac{1}{r} = \frac{1}{2}

with positive integers p \le q \le r, and show that the largest possible value of r is 42.

We can start by writing the following simple Python program to solve the problem, using integer arithmetic to avoid floating point problems:

from itertools import count
for r in count(1):
    for q in xrange(1, r + 1):
        for p in xrange(1, q + 1):
            # 1/p + 1/q + 1/r = 1/2
            # qr + pr + pq = pqr/2
            # 2(qr + pr + pq) = pqr
            if 2*(q*r + p*r + p*q) == p*q*r:
                print p, q, r

This program shows us ten possible values (including 42 in the last triple),

6 6 6
4 8 8
5 5 10
4 6 12
3 12 12
3 10 15
3 9 18
4 5 20
3 8 24
3 7 42

but, as it’s trying to enumerate all integer triples, it doesn’t halt.

To be sure not to miss any interesting integer triple, we must explore them more carefully:

from itertools import count
for p in count(1):
    # checks if we are leaving room for 1/q + 1/r
    # 1/p >= 1/2
    if 2 >= p:
        continue # we need smaller values of 1/p
    # checks if we can reach 1/2 with the biggest legal values for 1/q and 1/r
    # 1/p + 1/p + 1/p < 1/2
    if 3 * 2 < p: 
        break
    for q in count(p):
        # checks if we are leaving room for 1/r
        # 1/p + 1/q >= 1/2
        if 2 * (q + p) >= p * q: 
            continue
        # checks if we can reach 1/2 with the biggest legal value for 1/r
        # 1/p + 1/q + 1/q < 1/2
        if 2 * (q + 2 * p) < p * q:
            break
        for r in count(q):
            lhs = 2 * (q * r + p * r + p * q)
            rhs = p * q * r
            # 1/p + 1/q + 1/r > 1/2
            if lhs > rhs:
                continue
            # 1/p + 1/q + 1/r < 1/2
            elif lhs < rhs:
                break
            # 1/p + 1/q + 1/r = 1/2
            else:
                print p, q, r

The results are the same, but now we can be sure of having the whole solution.

Advertisements

A simple combinatorics problem

To break the long hiatus, I’m going to solve a short combinatorics problem extracted from “A Walk Through Combinatorics”:

Find all positive integers a < b < c such that \frac{1}{a} + \frac{1}{b} + \frac{1}{c} = 1.

As a is the smallest of the three integers, we know that \frac{1}{a} will be the bigger of the three fractions. The three fractions must add to one and they must be different, so \frac{1}{a} must be equal to \frac{1}{2}. Rewriting the restriction using this newly found knowledge:

\displaystyle \frac{1}{2} + \frac{1}{b} + \frac{1}{c} = 1

\displaystyle \frac{1}{b} + \frac{1}{c} = \frac{1}{2}.

b must be greater than 2, but it cannot be bigger than 3 because, otherwise,

\displaystyle \frac{1}{b} + \frac{1}{c} \leq \frac{1}{4} + \frac{1}{5} = \frac{9}{20} < \frac{1}{2}.

Then we have b = 3 and

\displaystyle c = \frac{1}{1 - \frac{1}{2} - \frac{1}{3}} = 6.