Maths Olympiad Prep

Library / Junior Balkan Mathematics Olympiad /11 of 15

Junior Balkan Mathematics Olympiad

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 4∣abcd‾4 \mid \overline{a b c d}.
We claim that 3∣abcd‾3 \mid \overline{a b c d}.
Assume a+b+c+d≡2(mod3)a+b+c+d \equiv 2 \pmod{3}. Then x+y≡1(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+d≡1(mod3)a+b+c+d \equiv 1 \pmod{3}. Then x+y≡2(mod3)x+y \equiv 2 \pmod{3}, for all distinct x,y∈{a,b,c,d}x, y \in \{a, b, c, d\}, and x≡1(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 4∣abcd‾4 \mid \overline{a b c d}, we have c=d=4c=d=4. Therefore, 8∣ab44‾8 \mid \overline{a b 44}, and since at least one more factor is even, it follows that 16∣ab44‾16 \mid \overline{a b 44}. Then b≠4b \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 11∣a744‾11 \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 3∣abcd‾3 \mid \overline{a b c d}, hence also 3∣a+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 3∣a+b+c+d−x−y3 \mid a+b+c+d-x-y, so 9∣abcd‾9 \mid \overline{a b c d}. Then 9∣a+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 xy≥x+y−1x y \geq x+y-1, valid for all x,y∈N∗x, 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 xy≥2(x+y)−4x y \geq 2(x+y)-4 for all x,y≥2x, y \geq 2, if a+b+c+d=18a+b+c+d=18 and all two-digit sums are greater than 11, then abcd‾≥323>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‾=1⋅17⋅8⋅92⋅10>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 8∣abcd‾8 \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 2⋅62⋅32⋅7=4536≠abcd‾2 \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 1⋅42⋅52⋅8=32001 \cdot 4^2 \cdot 5^2 \cdot 8=3200, 2⋅3⋅4⋅5⋅6⋅7=50402 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7=5040 and 22⋅5⋅4⋅72=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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.