Maths Olympiad Prep

Library / /5 of 18

Number theory Difficulty 5.2 AIME, harder Find the answer Italy

Problem:

Determine the number of ordered triples (a,b,c)(a, b, c) of nonnegative integers such that each of the numbers 2a2^{a}, 2b2^{b}, 2c2^{c} is less than 1000010000 and the number 2a+2b+2c2^{a}+2^{b}+2^{c} is a divisor of 8a+8b+8c8^{a}+8^{b}+8^{c}.

Pick one

Solution

Solution:

The answer is (E)\mathbf{( E )}. Let us start by observing that the following algebraic identity holds
x3+y3+z33xyz=(x+y+z)(x2+y2+z2xyyzxz) x^{3}+y^{3}+z^{3}-3 x y z=(x+y+z)\left(x^{2}+y^{2}+z^{2}-x y-y z-x z\right)
Setting x=2ax=2^{a}, y=2by=2^{b}, z=2cz=2^{c}, the condition x+y+zx3+y3+z3x+y+z \mid x^{3}+y^{3}+z^{3} is equivalent to x+y+z3xyzx+y+z \mid 3 x y z; in particular, we want to look for the triples (a,b,c)(a, b, c) such that 2a+2b+2c32a+b+c2^{a}+2^{b}+2^{c} \mid 3 \cdot 2^{a+b+c}.
If we assume abca \leq b \leq c, simplifying a 2a2^{a} we obtain that 1+2ba+2ca32b+c1+2^{b-a}+2^{c-a} \mid 3 \cdot 2^{b+c}. If it were b>ab>a, on the left we would have an odd number 5\geq 5, while on the right a number whose odd part is 3, which is impossible. Hence b=ab=a holds and we must find the solutions of 2+2ca32c+a2+2^{c-a} \mid 3 \cdot 2^{c+a}. At this point we split into four cases

- If c=ac=a, 2+1322a2+1 \mid 3 \cdot 2^{2 a} is always satisfied, so we have all triples of the form (a,a,a)(a, a, a) with 0a130 \leq a \leq 13 (since 213<10000<2142^{13}<10000<2^{14} ), which are 14.

- If c=a+1c=a+1, we can rewrite the condition as 2+2322a+12+2 \mid 3 \cdot 2^{2 a+1}, which holds for a1a \geq 1 and from which we obtain the triples (a,a,a+1)(a, a, a+1) and their permutations; hence this case has in total 3123 \cdot 12 solutions (since we also need a+113a+1 \leq 13)

- If c=a+2c=a+2, the condition becomes 2+4322a+22+4 \mid 3 \cdot 2^{2 a+2}, which holds for a0a \geq 0. We thus obtain the triples (a,a,a+2)(a, a, a+2) and their permutations, which are valid up to a+213a+2 \leq 13, hence 3123 \cdot 12 solutions in this case as well.

- If ca+3c \geq a+3, letting d=ca1d=c-a-1 we have 1+2d322a+d1+2^{d} \mid 3 \cdot 2^{2 a+d}. Since d2d \geq 2, the number on the left is odd and 5\geq 5, so there are no solutions.

The total number of ordered triples is therefore 14+36+36=8614+36+36=86.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.