56th International Mathematical Olympiad Shortlisted Problems

It can easily be verified that these sixteen triples are as required. Now let $(a,b,c)$ be any triple with the desired property. If we would have $a=1$, then both $b-c$ and $c-b$ were powers of $2$, which is impossible since their sum is zero; because of symmetry, this argument shows $a,b,c⩾2$.

Case 1. Among $a,b$, and $c$ there are at least two equal numbers.

Without loss of generality we may suppose that $a=b$. Then $a^2-c$ and $a(c-1)$ are powers of $2$. The latter tells us that actually $a$ and $c-1$ are powers of $2$. So there are nonnegative integers $\alpha$ and $\gamma$ with $a=2^{\alpha }$ and $c=2^{\gamma }+1$. Since $a^2-c=2^{2\alpha }-2^{\gamma }-1$ is a power of $2$ and thus incongruent to $-1$ modulo $4$, we must have $\gamma ⩽1$. Moreover, each of the terms $2^{2\alpha }-2$ and $2^{2\alpha }-3$ can only be a power of $2$ if $\alpha =1$. It follows that the triple $(a,b,c)$ is either $(2,2,2)$ or $(2,2,3)$.

Case 2. The numbers $a,b$, and $c$ are distinct.

Due to symmetry we may suppose that $$2⩽a<b<c$$ We are to prove that the triple $(a,b,c)$ is either $(2,6,11)$ or $(3,5,7)$. By our hypothesis, there exist three nonnegative integers $\alpha ,\beta$, and $\gamma$ such that $$\begin{array}{rl}bc-a& =2^{\alpha },\\ ac-b& =2^{\beta },\\ \text{and}ab-c& =2^{\gamma }.\end{array}$$ Evidently we have $$\alpha >\beta >\gamma .$$ Depending on how large $a$ is, we divide the argument into two further cases.

Case 2.1. $a=2$.

We first prove that $\gamma =0$. Assume for the sake of contradiction that $\gamma >0$. Then $c$ is even by (4) and, similarly, $b$ is even by (5) and (3). So the left-hand side of (2) is congruent to $2$ modulo $4$, which is only possible if $bc=4$. As this contradicts (1), we have thereby shown that $\gamma =0$, i.e., that $c=2b-1$.

Now (3) yields $3b-2=2^{\beta }$. Due to $b>2$ this is only possible if $\beta ⩾4$. If $\beta =4$, then we get $b=6$ and $c=2\cdot 6-1=11$, which is a solution. It remains to deal with the case $\beta ⩾5$. Now (2) implies $$9\cdot 2^{\alpha }=9b(2b-1)-18=(3b-2)(6b+1)-16=2^{\beta }(2^{\beta +1}+5)-16$$ and by $\beta ⩾5$ the right-hand side is not divisible by $32$. Thus $\alpha ⩽4$ and we get a contradiction to (5).

Case 2.2. $a⩾3$.

Pick an integer $\vartheta \in \{-1,+1\}$ such that $c-\vartheta$ is not divisible by $4$. Now $$2^{\alpha }+\vartheta \cdot 2^{\beta }=(bc-a{\vartheta }^2)+\vartheta (ca-b)=(b+a\vartheta )(c-\vartheta )$$ is divisible by $2^{\beta }$ and, consequently, $b+a\vartheta$ is divisible by $2^{\beta -1}$. On the other hand, $2^{\beta }=ac-b>(a-1)c⩾2c$ implies in view of (1) that $a$ and $b$ are smaller than $2^{\beta -1}$. All this is only possible if $\vartheta =1$ and $a+b=2^{\beta -1}$. Now (3) yields $$ac-b=2(a+b)$$ whence $4b>a+3b=a(c-1)⩾ab$, which in turn yields $a=3$.

So (6) simplifies to $c=b+2$ and (2) tells us that $b(b+2)-3=(b-1)(b+3)$ is a power of $2$. Consequently, the factors $b-1$ and $b+3$ are powers of $2$ themselves. Since their difference is $4$, this is only possible if $b=5$ and thus $c=7$. Thereby the solution is complete.

---

Alternative solution.

As in the beginning of the first solution, we observe that $a,b,c⩾2$. Depending on the parities of $a,b$, and $c$ we distinguish three cases.

Case 1. The numbers $a,b$, and $c$ are even.

Let $2^A,2^B$, and $2^C$ be the largest powers of $2$ dividing $a,b$, and $c$ respectively. We may assume without loss of generality that $1⩽A⩽B⩽C$. Now $2^B$ is the highest power of $2$ dividing $ac-b$, whence $ac-b=2^B⩽b$. Similarly, we deduce $bc-a=2^A⩽a$. Adding both estimates we get $(a+b)c⩽2(a+b)$, whence $c⩽2$. So $c=2$ and thus $A=B=C=1$; moreover, we must have had equality throughout, i.e., $a=2^A=2$ and $b=2^B=2$. We have thereby found the solution $(a,b,c)=(2,2,2)$.

Case 2. The numbers $a,b$, and $c$ are odd.

If any two of these numbers are equal, say $a=b$, then $ac-b=a(c-1)$ has a nontrivial odd divisor and cannot be a power of $2$. Hence $a,b$, and $c$ are distinct. So we may assume without loss of generality that $a<b<c$.

Let $\alpha$ and $\beta$ denote the nonnegative integers for which $bc-a=2^{\alpha }$ and $ac-b=2^{\beta }$ hold. Clearly, we have $\alpha >\beta$, and thus $2^{\beta }$ divides $$a\cdot 2^{\alpha }-b\cdot 2^{\beta }=a(bc-a)-b(ac-b)=b^2-a^2=(b+a)(b-a).$$ Since $a$ is odd, it is not possible that both factors $b+a$ and $b-a$ are divisible by $4$. Consequently, one of them has to be a multiple of $2^{\beta -1}$. Hence one of the numbers $2(b+a)$ and $2(b-a)$ is divisible by $2^{\beta }$ and in either case we have $$ac-b=2^{\beta }⩽2(a+b).$$ This in turn yields $(a-1)b<ac-b<4b$ and thus $a=3$ (recall that $a$ is odd and larger than $1$). Substituting this back into (7) we learn $c⩽b+2$. But due to the parity $b<c$ entails that $b+2⩽c$ holds as well. So we get $c=b+2$ and from $bc-a=(b-1)(b+3)$ being a power of $2$ it follows that $b=5$ and $c=7$.

Case 3. Among $a,b$, and $c$ both parities occur.

Without loss of generality, we suppose that $c$ is odd and that $a⩽b$. We are to show that $(a,b,c)$ is either $(2,2,3)$ or $(2,6,11)$. As at least one of $a$ and $b$ is even, the expression $ab-c$ is odd; since it is also a power of $2$, we obtain $$ab-c=1.$$ If $a=b$, then $c=a^2-1$, and from $ac-b=a(a^2-2)$ being a power of $2$ it follows that both $a$ and $a^2-2$ are powers of $2$, whence $a=2$. This gives rise to the solution $(2,2,3)$.

We may suppose $a<b$ from now on. As usual, we let $\alpha >\beta$ denote the integers satisfying $$2^{\alpha }=bc-a\text{and}{2}^{\beta }=ac-b$$ If $\beta =0$ it would follow that $ac-b=ab-c=1$ and hence that $b=c=1$, which is absurd. So $\beta$ and $\alpha$ are positive and consequently $a$ and $b$ are even. Substituting $c=ab-1$ into (9) we obtain $$\begin{array}{rl}{2}^{\alpha }& =a{b}^2-(a+b)\\ 2^{\beta }& =a^{2}b-(a+b)\end{array}$$ The addition of both equation yields $2^{\alpha }+2^{\beta }=(ab-2)(a+b)$. Now $ab-2$ is even but not divisible by $4$, so the highest power of $2$ dividing $a+b$ is $2^{\beta -1}$. For this reason, the equations (10) and (11) show that the highest powers of $2$ dividing either of the numbers $a{b}^2$ and $a^{2}b$ is likewise $2^{\beta -1}$. Thus there is an integer $\tau ⩾1$ together with odd integers $A,B$, and $C$ such that $a=2^{\tau }A,b=2^{\tau }B,a+b=2^{3\tau }C$, and $\beta =1+3\tau$.

Notice that $A+B=2^{2\tau }C⩾4C$. Moreover, (11) entails $A^{2}B-C=2$. Thus $8=4A^{2}B-4C⩾4A^{2}B-A-B⩾A^2(3B-1)$. Since $A$ and $B$ are odd with $A<B$, this is only possible if $A=1$ and $B=3$. Finally, one may conclude $C=1,\tau =1,a=2,b=6$, and $c=11$. We have thereby found the triple $(2,6,11)$. This completes the discussion of the third case, and hence the solution.