Maths Olympiad Prep

Library / /92 of 105

Number theory Difficulty 6.9 National Olympiad Prove it JBMO

Problem:

Vukasin, Dimitrije, Dusan, Stefan and Filip asked their professor to guess three consecutive positive integer numbers after they had told him these (true) sentences:

Vukasin: "Sum of the digits of one of them is a prime number. Sum of the digits of some of the other two is an even perfect number (nn is perfect if σ(n)=2n\sigma(n) = 2n). Sum of the digits of the remaining number is equal to the number of its positive divisors."

Dimitrije: "Each of these three numbers has no more than two digits 1 in its decimal representation."

Dusan: "If we add 11 to one of them, we obtain a square of an integer."

Stefan: "Each of them has exactly one prime divisor less than 10."

Filip: "The 3 numbers are square-free."

Their professor gave the correct answer. Which numbers did he say?

Solution

Solution:

Let the middle number be nn, so the numbers are n1n-1, nn and n+1n+1. Since 44 does not divide any of them, n2(mod4)n \equiv 2 \pmod{4}. Furthermore, neither 33, 55 nor 77 divides nn. Also n+1+112(mod4)n+1+11 \equiv 2 \pmod{4} cannot be a square. Then 33 must divide n1n-1 or n+1n+1. If n1+11n-1+11 is a square, then 3n+13 \mid n+1 which implies 3n+103 \mid n+10 (a square), so 9n+109 \mid n+10 hence 9n+19 \mid n+1, which is impossible. Thus must be n+11=m2n+11 = m^2.

Further, 77 does not divide n1n-1, nor n+1n+1, because 1+115(mod7)1+11 \equiv 5 \pmod{7} and 1+113(mod7)-1+11 \equiv 3 \pmod{7} are quadratic nonresidues modulo 77. This implies 5n15 \mid n-1 or 5n+15 \mid n+1. Again, since n+11n+11 is a square, it is impossible 5n15 \mid n-1, hence 5n+15 \mid n+1 which implies 3n13 \mid n-1. This yields n4(mod10)n \equiv 4 \pmod{10} hence S(n+1)=S(n)+1=S(n1)+2S(n+1) = S(n) + 1 = S(n-1) + 2 (S(n)S(n) is sum of the digits of nn).

Since the three numbers are square-free, their numbers of positive divisors are powers of 22. Thus, we have two even sums of digits - they must be S(n1)S(n-1) and S(n+1)S(n+1), so S(n)S(n) is prime. From 3n13 \mid n-1, follows S(n1)S(n-1) is an even perfect number, and S(n+1)=2pS(n+1) = 2^p. Consequently S(n)=2p1S(n) = 2^p - 1 is a prime, so pp is a prime number. One easily verifies p2p \neq 2, so pp is odd implying 32p23 \mid 2^p - 2. Then

σ(2p2)(2p2)(1+12+13+16)=2(2p2)\sigma\left(2^p - 2\right) \geq \left(2^p - 2\right)\left(1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{6}\right) = 2\left(2^p - 2\right). Since this number is perfect, 2p26\frac{2^p - 2}{6} must be one, i.e. p=3p = 3 and S(n1)=6S(n-1) = 6, S(n)=7S(n) = 7 and S(n+1)=8S(n+1) = 8.

Since 44 does not divide nn, the 22-digit ending of nn must be 1414 or 3434. But n=34n = 34 is impossible, since n+11=45n+11 = 45 is not a square. Hence, n=10a+10b+14n = 10^a + 10^b + 14 with ab2a \geq b \geq 2. If aba \neq b, then nn has three digits 11 in its decimal representation, which is impossible. Therefore a=ba = b, and n=210a+14n = 2 \cdot 10^a + 14. Now, 210a+25=m22 \cdot 10^a + 25 = m^2, hence 5m5 \mid m, say m=5tm = 5t, and (t1)(t+1)=2a+15a2(t-1)(t+1) = 2^{a+1} 5^{a-2}. Because gcd(t1,t+1)=2\gcd(t-1, t+1) = 2 there are three possibilities:

1) t1=2t-1 = 2, t+1=2a5a2t+1 = 2^a 5^{a-2}, which implies a=2a = 2, t=3t = 3;
2) t1=2at-1 = 2^a, t+1=25a2t+1 = 2 \cdot 5^{a-2}, so 2a+2=25a22^a + 2 = 2 \cdot 5^{a-2}, which implies a=3a = 3, t=9t = 9;
3) t1=25a2t-1 = 2 \cdot 5^{a-2}, t+1=2at+1 = 2^a, so 25a2+2=2a2 \cdot 5^{a-2} + 2 = 2^a, which implies a=2a = 2, t=3t = 3, same as case 1.

From the only two possibilities (n1,n,n+1)=(213,214,215)(n-1, n, n+1) = (213, 214, 215) and (n1,n,n+1)=(2013,2014,2015)(n-1, n, n+1) = (2013, 2014, 2015) the first one is not possible, because S(215)=8S(215) = 8 and τ(215)=4\tau(215) = 4. By checking the conditions, we conclude that the latter is a solution, so the professor said the numbers: 20132013, 20142014, 20152015.

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.