# Exhaustion

Find the positive integer solutions of the equation (1+1/a)(1+1/b)(1+1/c) = 2

Find the positive integer solutions of the equation

\[ \left(1 + \frac{1}{a}\right)\left(1 + \frac{1}{b}\right) \left(1+ \frac{1}{c}\right) = 2. \]

*This problem was taken from the Hungarian magazine KoMaL. There are many other challenging problems in English on the KoMal website.*

Perhaps you might like to try the problem Unit Fractions first.

What value does the expression take for small values of a?

What value does the expression take for large values of a?

When you try a particular value for a what can you say about b?

Once you have narrowed down the possible values, you have to test all possible cases; this is known as proof by exhaustion.

Eduardo and Arvind both looked for solutions by restricting their search to the case $a< b< c$ and working out the limitations this gave them for values of $a,b$ and $c$. Both of them found a solution $a=3, b=4, c=5$ by this method.

Kai rewrote $\left(1+\frac{1}{a}\right)$ as $\frac{a+1}{a}$:

I first realised $\left(1+\frac{1}{a}\right)$ is the same as $\frac{a+1}{a}$. So I set about trying to find to consecutive non-prime numbers. I would then divide them into 2 and try to find two other numbers $\left(1+\frac{1}{b}\right)$ and $\left(1+\frac{1}{c}\right)$ that multiply together to get this number. I found 8 and 9 first and put that in: $2\div \frac{9}{8} = 2\times \frac{8}{9} = \frac{16}{9}$. This number has a non-prime numerator and denominator. As $\frac{4}{3} \times \frac{4}{3} = \frac{16}{9}$, there is a solution: $a = 8, b = 3, c = 3$

Kai used a similar method to find the solution $a=15, b=2, c=4$.

Ming Chen and Thomas both used exhaustive methods to find all the possibilities. Here is Thomas's solution:

I tried to solve this by the process of exhaustion, using several known facts.

First, a, b, and c are integers greater than zero: $a, b, c > 0 \Rightarrow \frac{1}{a}, \frac{1}{b}, \frac{1}{c} > 0$

so $1 + \frac{1}{a}, 1 + \frac{1}{b}$ and $1 + \frac{1}{c}$ are all greater than $1$.

We can assume $a \leq b \leq c$ (because the three brackets can be written in any order), which implies that $a> 1$, because if $a=1$, $1 + \frac{1}{a}=2$. $1 + \frac{1}{b}$ and $1 + \frac{1}{c}$ are both strictly greater than $1$, so the product would be greater than $2$.

Next, we find the greatest value for $a$.

If $a$ is the smallest, then $1 + \frac{1}{a}$ must be the largest term. This can also be written $\frac{a+1}{a}$.

The largest possible value of $a$ is the case, $a = b= c$.

Any whole number value of $a$ greater than 3 will result in a product less than 2: $(\frac{4}{3})^3 = 2.37...$ and $(\frac{5}{4})^3 = 1.95...$

Thus we have proved that $2 \leq a \leq 3$, so $a$ must be either $2$ or $3$.

Assuming that $a$ is 2, we have $(1+\frac{1}{c})\times(1+\frac{1}{b}) = \frac{4}{3}$.

Using the same logic, $(\frac{b+1}{ b})^2 \geq 4/3$, thus the greatest value for $b$ must be $6$, as $(\frac{7}{6})^2 = 1.36.. > \frac{4}{3}$ and $(\frac{8}{7})^2 = 1.31.. < \frac{4}{3}$.

Similarly, $b > 3$, as $\frac{c+1}{c} > 1$, and for $b \leq 3$ we would need $c \leq 1$ for the product to be $\frac{4}{3}$.

We have now proved $4 \leq b \leq 6$.

Now we just solve for $c$, using $\frac{3}{2}\times(1 + \frac{1}{b}\times c = 2$,with $b=4,5,6$ giving us the triples $(2, 4, 15) (2, 5, 9) (2, 6, 7)$, and their permutations (as we assumed $a \leq b \leq c$).

Finally, assuming that $a$ is now $3$, $(1+\frac{1}{c})\times(1+\frac{1}{b}) = \frac{3}{2}$, and we follow the same logic as above to restrict the value of $b$ to $3$ or $4$. Then we solve for $c$ accordingly, giving us $(3, 3, 8), (3, 4, 5)$ and their permutations.

Therefore, we have proved that there are $5$ unique triples of $a, b, c$ required to achieve $\left(1+\frac{1}{a}\right)\left(1+\frac{1}{b}\right)\left(1+\frac{1}{c}\right)=2$

and there are in total $5 \times (3!)$ or 30 total triples by interchanging values between $a, b,$ and $c$.