Maths Olympiad Prep

Library / /12 of 16

Number theory Difficulty 7.0 National Olympiad Prove it JBMO

Problem:
Determine all four-digit numbers abcd\overline{a b c d} such that
(a+b)(a+c)(a+d)(b+c)(b+d)(c+d)=abcd (a+b)(a+c)(a+d)(b+c)(b+d)(c+d)=\overline{a b c d}

Solution

Solution:
Depending on the parity of a,b,c,da, b, c, d, at least two of the factors (a+b),(a+c),(a+d),(b+c),(b+d),(c+d)(a+b), (a+c), (a+d), (b+c), (b+d), (c+d) are even, so that 4abcd4 \mid \overline{a b c d}.
We claim that 3abcd3 \mid \overline{a b c d}.
Assume a+b+c+d2(mod3)a+b+c+d \equiv 2 \pmod{3}. Then x+y1(mod3)x+y \equiv 1 \pmod{3}, for all distinct x,y{a,b,c,d}x, y \in \{a, b, c, d\}. But then the left hand side in the above equality is congruent to 1(mod3)1 \pmod{3} and the right hand side congruent to 2(mod3)2 \pmod{3}, contradiction.
Assume a+b+c+d1(mod3)a+b+c+d \equiv 1 \pmod{3}. Then x+y2(mod3)x+y \equiv 2 \pmod{3}, for all distinct x,y{a,b,c,d}x, y \in \{a, b, c, d\}, and x1(mod3)x \equiv 1 \pmod{3}, for all x,y{a,b,c,d}x, y \in \{a, b, c, d\}. Hence, a,b,c,d{1,4,7}a, b, c, d \in \{1,4,7\}, and since 4abcd4 \mid \overline{a b c d}, we have c=d=4c=d=4. Therefore, 8ab448 \mid \overline{a b 44}, and since at least one more factor is even, it follows that 16ab4416 \mid \overline{a b 44}. Then b4b \neq 4, and the only possibilities are b=1b=1, implying a=4a=4, which is impossible because 41444144 is not divisible by 5=1+45=1+4, or b=7b=7, implying 11a74411 \mid \overline{a 744}, hence a=7a=7, which is also impossible because 77447744 is not divisible by 14=7+714=7+7.
We conclude that 3abcd3 \mid \overline{a b c d}, hence also 3a+b+c+d3 \mid a+b+c+d. Then at least one factor x+yx+y of (a+b),(a+c),(a+d),(b+c),(b+d),(c+d)(a+b),(a+c),(a+d),(b+c),(b+d),(c+d) is a multiple of 33, implying that also 3a+b+c+dxy3 \mid a+b+c+d-x-y, so 9abcd9 \mid \overline{a b c d}. Then 9a+b+c+d9 \mid a+b+c+d, and a+b+c+d{9,18,27,36}a+b+c+d \in \{9,18,27,36\}. Using the inequality xyx+y1x y \geq x+y-1, valid for all x,yNx, y \in \mathbb{N}^*, if a+b+c+d{27,36}a+b+c+d \in \{27,36\}, then
abcd=(a+b)(a+c)(a+d)(b+c)(b+d)(c+d)263>104 \overline{a b c d}=(a+b)(a+c)(a+d)(b+c)(b+d)(c+d) \geq 26^3>10^4
which is impossible.
Using the inequality xy2(x+y)4x y \geq 2(x+y)-4 for all x,y2x, y \geq 2, if a+b+c+d=18a+b+c+d=18 and all two-digit sums are greater than 11, then abcd323>104\overline{a b c d} \geq 32^3>10^4. Hence, if a+b+c+d=18a+b+c+d=18, some two-digit sum must be 11, hence the complementary sum will be 1717, and the digits are {a,b,c,d}={0,1,8,9}\{a, b, c, d\}=\{0,1,8,9\}. But then abcd=11789210>104\overline{a b c d}=1 \cdot 17 \cdot 8 \cdot 9^2 \cdot 10>10^4.
We conclude that a+b+c+d=9a+b+c+d=9. Then among a,b,c,da, b, c, d there are either three odd or three even numbers, and 8abcd8 \mid \overline{a b c d}.
If three of the digits are odd, then dd is even and since cc is odd, divisibility by 88 implies that d{2,6}d \in \{2,6\}. If d=6d=6, then a=b=c=1a=b=c=1. But 11161116 is not divisible by 77, so this is not a solution. If d=2d=2, then a,b,ca, b, c are either 1,1,51,1,5 or 1,3,31,3,3 in some order. In the first case 262327=4536abcd2 \cdot 6^2 \cdot 3^2 \cdot 7=4536 \neq \overline{a b c d}. The second case cannot hold because the resulting number is not a multiple of 55.
Hence, there has to be one odd and three even digits. At least one of the two-digit sums of even digits is a multiple of 44, and since there cannot be two zero digits, we have either x+y=4x+y=4 and z+t=5z+t=5, or x+y=8x+y=8 and z+t=1z+t=1 for some ordering x,y,z,tx, y, z, t of a,b,c,da, b, c, d. In the first case we have d=0d=0 and the digits are 0,1,4,40,1,4,4, or 0,2,3,40,2,3,4, or 0,2,2,50,2,2,5. None of these is a solution because 142528=32001 \cdot 4^2 \cdot 5^2 \cdot 8=3200, 234567=50402 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7=5040 and 225472=39202^2 \cdot 5 \cdot 4 \cdot 7^2=3920. In the second case two of the digits are 00 and 11, and the other two have to be either 44 and 44, or 22 and 66. We already know that the first possibility fails. For the second, we get
(0+1)(0+2)(0+6)(1+2)(1+6)(2+6)=2016 (0+1) \cdot (0+2) \cdot (0+6) \cdot (1+2) \cdot (1+6) \cdot (2+6)=2016
and abcd=2016\overline{a b c d}=2016 is the only solution.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.