Maths Olympiad Prep

Library / /428 of 520

Number theory Difficulty 7.4 National olympiad, round 2 Find the answer

Call a number nn good if it can be expressed as 2x+y22^x+y^2 for where xx and yy are nonnegative integers.
(a) Prove that there exist infinitely many sets of 44 consecutive good numbers.
(b) Find all sets of 55 consecutive good numbers.

Proposed by Michael Ma

A number or a short expression. Spacing and $ signs are ignored.

Solution

(a) We claim that (a21,a2,a2+1,a2+2)(a^2-1, a^2, a^2+1, a^2+2) works for a=2n+1a = 2^n + 1 where n1n \ge 1. Indeed, we can verify each number in the set:

1. a21=(2n+1)21=22n+2n+1+11=2n+1+(2n)2a^2 - 1 = (2^n + 1)^2 - 1 = 2^{2n} + 2^{n+1} + 1 - 1 = 2^{n+1} + (2^n)^2
2. a2=(2n+1)2=22n+2n+1+1=2n+2+(2n1)2a^2 = (2^n + 1)^2 = 2^{2n} + 2^{n+1} + 1 = 2^{n+2} + (2^n - 1)^2
3. a2+1=(2n+1)2+1=22n+2n+1+1+1=20+a2a^2 + 1 = (2^n + 1)^2 + 1 = 2^{2n} + 2^{n+1} + 1 + 1 = 2^0 + a^2
4. a2+2=(2n+1)2+2=22n+2n+1+1+2=21+a2a^2 + 2 = (2^n + 1)^2 + 2 = 2^{2n} + 2^{n+1} + 1 + 2 = 2^1 + a^2

Thus, all four numbers are good, proving that there are infinitely many sets of 4 consecutive good numbers.

(b) We claim that the solutions are (1,2,3,4,5)(1, 2, 3, 4, 5), (2,3,4,5,6)(2, 3, 4, 5, 6), (8,9,10,11,12)(8, 9, 10, 11, 12), (9,10,11,12,13)(9, 10, 11, 12, 13), (288,289,290,291,292)(288, 289, 290, 291, 292), and (289,290,291,292,293)(289, 290, 291, 292, 293).

To prove this, we need to show that these sets are the only possible sets of 5 consecutive good numbers. We start by examining the function f(n)=(2n+1)2+3f(n) = (2^n + 1)^2 + 3 and show that it is good if and only if n=1n = 1 or n=4n = 4.

Proof:
1. For n=1n = 1, f(1)=(21+1)2+3=32+3=9+3=12=22+22f(1) = (2^1 + 1)^2 + 3 = 3^2 + 3 = 9 + 3 = 12 = 2^2 + 2^2, which is good.
2. For n=4n = 4, f(4)=(24+1)2+3=172+3=289+3=292=28+62f(4) = (2^4 + 1)^2 + 3 = 17^2 + 3 = 289 + 3 = 292 = 2^8 + 6^2, which is good.

Now, assume n4n \ge 4 and suppose f(n)f(n) is good, i.e., (2n+1)2+3=2x+y2(2^n + 1)^2 + 3 = 2^x + y^2. This implies:
y2=22n+2n+1+42x y^2 = 2^{2n} + 2^{n+1} + 4 - 2^x

We split into cases based on the value of xx:

Case 1: xn+1x \le n + 1
- Subcase 1.1: x=0x = 0
y2=22n+2n+1+3=(2n+1)2+2 y^2 = 2^{2n} + 2^{n+1} + 3 = (2^n + 1)^2 + 2
No two squares differ by 2, so no solutions here.

- Subcase 1.2: x=1x = 1
y2=22n+2n+1+2=(2n+1)2+1 y^2 = 2^{2n} + 2^{n+1} + 2 = (2^n + 1)^2 + 1
No two squares differ by 1, so no solutions here.

- Subcase 1.3: 2xn+12 \le x \le n + 1
(2n)2<y2<(2n+1)2 (2^n)^2 < y^2 < (2^n + 1)^2
This means there are no solutions here.

Case 2: xn+2x \ge n + 2
Let x=n+1+αx = n + 1 + \alpha where α1\alpha \ge 1. We see from the equation that yy is even, so let y=2zy = 2z. Furthermore, let m=n1m = n - 1. The equation reduces to:
z2=22m2m(2α1)+1 z^2 = 2^{2m} - 2^m(2^\alpha - 1) + 1
This means that zz is odd and less than 2m2^m, so let z=2mkz = 2^m - k where k1k \ge 1 is odd. Then,
z2=22m2m(2k)+k2 z^2 = 2^{2m} - 2^m(2k) + k^2
2m(2k2α+1)=(k1)(k+1) 2^m(2k - 2^\alpha + 1) = (k - 1)(k + 1)

We have some subcases:

- Subcase 2.1: k1(mod4)k \equiv 1 \pmod{4}
2m(k1)(k+1) 2^m \mid (k - 1)(k + 1)
2m1(k1)(k+12) 2^{m-1} \mid (k - 1)(\frac{k + 1}{2})
Since (k+1)/2(k + 1)/2 is odd, we have 2m1k12^{m-1} \mid k - 1, so write k=1+2m1βk = 1 + 2^{m-1}\beta, where β0\beta \ge 0. Plugging this into the equation gives:
2mβ2α+3=2m2β2+β 2^m\beta - 2^\alpha + 3 = 2^{m-2}\beta^2 + \beta
The left side is odd, so the right side is odd. Since m=n13m = n - 1 \ge 3, β\beta must be odd.

- Subcase 2.1.1: β=1\beta = 1
2m2α+3=2m2+1 2^m - 2^\alpha + 3 = 2^{m-2} + 1
3(2m2+1)=2α+1 3(2^{m-2} + 1) = 2^\alpha + 1
This has the unique solution m=3m = 3 and α=3\alpha = 3. This gives n=4n = 4, which is a solution.

- Subcase 2.1.2: β=3\beta = 3
32m2α+3=2m29+3 3 \cdot 2^m - 2^\alpha + 3 = 2^{m-2} \cdot 9 + 3
32m2=2α 3 \cdot 2^{m-2} = 2^\alpha
This has no solutions.

- Subcase 2.1.3: β5\beta \ge 5
32α=2m2(β24β)+β52m210 3 - 2^\alpha = 2^{m-2}(\beta^2 - 4\beta) + \beta \ge 5 \cdot 2^{m-2} \ge 10
This has no solutions.

- Subcase 2.2: k3(mod4)k \equiv 3 \pmod{4}
2m(k1)(k+1) 2^m \mid (k - 1)(k + 1)
2m1(k+1)(k12) 2^{m-1} \mid (k + 1)(\frac{k - 1}{2})
Since (k1)/2(k - 1)/2 is odd, we have 2m1k+12^{m-1} \mid k + 1, so write k=1+2m1βk = -1 + 2^{m-1}\beta, where β1\beta \ge 1. Plugging this into the equation gives:
2mβ2α1=2m2β2β 2^m\beta - 2^\alpha - 1 = 2^{m-2}\beta^2 - \beta
The left side is odd, so the right side is odd. Since m=n13m = n - 1 \ge 3, β\beta must be odd.

- Subcase 2.2.1: β=1\beta = 1
2m2α1=2m2+1 2^m - 2^\alpha - 1 = 2^{m-2} + 1
32m2=2α 3 \cdot 2^{m-2} = 2^\alpha
This has no solutions.

- Subcase 2.2.2: β=3\beta = 3
32m2α1=2m293 3 \cdot 2^m - 2^\alpha - 1 = 2^{m-2} \cdot 9 - 3
2m23=2α2 2^{m-2} \cdot 3 = 2^\alpha - 2
For the right side to be divisible by 3, we need 3α3 \mid \alpha.

- Subcase 2.2.2.1: α=3\alpha = 3
We get m=3m = 3, so n=4n = 4, which is a solution.

- Subcase 2.2.2.2: α6\alpha \ge 6
The right side is 2(mod4)2 \pmod{4}, so we must have m=3m = 3. But this is a contradiction to size, so no solutions here.

- Subcase 2.2.3: β5\beta \ge 5
12α=2m2(β24β)β2(β24β)β5 -1 - 2^\alpha = 2^{m-2}(\beta^2 - 4\beta) - \beta \ge 2(\beta^2 - 4\beta) - \beta \ge 5
This has no solutions.

This completes all the cases, so the only solution for n4n \ge 4 is n=4n = 4. This completes the proof of the claim. \blacksquare

Let's return to solving the original problem. We'll be needing two recurring lemmas.

Lemma: Suppose nn is good. Then, n2(mod4)n \equiv 2 \pmod{4} implies either n=a2+1n = a^2 + 1 for odd aa, or n=a2+2n = a^2 + 2 for even aa. Similarly, if n3(mod4)n \equiv 3 \pmod{4}, then n=a2+2n = a^2 + 2 for odd aa.

Proof: The key is that if x2x \ge 2, then 2x+y0,1(mod4)2^x + y \equiv 0, 1 \pmod{4}. So if n=2x+y2,3(mod4)n = 2^x + y \equiv 2, 3 \pmod{4}, then x=0x = 0 or x=1x = 1. Working out the details of mod 44 gives the result. \blacksquare

Lemma: Suppose a2a^2 is good where aa is odd. Then either a=1a = 1, or a=2n+1a = 2^n + 1 for some n1n \ge 1.

Proof: Suppose a2=2x+y2a^2 = 2^x + y^2 where x1x \ge 1. Then, we have a2=2x+y2a^2 = 2^x + y^2, so
(ay)(a+y)=2x (a - y)(a + y) = 2^x
Now, aya+y(mod2)a - y \equiv a + y \pmod{2}, and since x1x \ge 1, this means that they both must be even. Thus, ay=2pa - y = 2^p and a+y=2qa + y = 2^q for some p,q1p, q \ge 1, so a=2p+2q2a = \frac{2^p + 2^q}{2}. Since aa is odd, this means a=2n+1a = 2^n + 1 for some n1n \ge 1.

Now, if x=1x = 1, then a2=1+y2a^2 = 1 + y^2. This means y=0y = 0 and a=1a = 1, as desired. This completes the proof of the lemma. \blacksquare

Suppose that (a1,a2,a3,a4,a5)(a_1, a_2, a_3, a_4, a_5) are 5 consecutive positive integers that are all good. We have 4 cases.

Case 1: Suppose a10(mod4)a_1 \equiv 0 \pmod{4}. We see that a43(mod4)a_4 \equiv 3 \pmod{4} is good, so a4=a2+2a_4 = a^2 + 2 for some odd aa. Thus, the numbers (a21,a2,a2+1,a2+2,a2+3)(a^2 - 1, a^2, a^2 + 1, a^2 + 2, a^2 + 3) are all good. Thus, a2a^2 is good and aa odd, so a=1a = 1 or a=2n+1a = 2^n + 1 for n1n \ge 1. We can't have a=1a = 1 as 121=01^2 - 1 = 0 is not good, so we must have a=2n+1a = 2^n + 1. Thus, a2+3=(2n+1)2+3a^2 + 3 = (2^n + 1)^2 + 3 is good, so by the claim, we have either n=1n = 1 or n=4n = 4. These give the two solutions:
(8,9,10,11,12)and(288,289,290,291,292) \boxed{(8, 9, 10, 11, 12) \quad \text{and} \quad (288, 289, 290, 291, 292)}

Case 2: Suppose a11(mod4)a_1 \equiv 1 \pmod{4}. We see that a33(mod4)a_3 \equiv 3 \pmod{4} is good, so a3=a2+2a_3 = a^2 + 2 for some odd aa. Thus, the numbers (a2,a2+1,a2+2,a2+3,a2+4)(a^2, a^2 + 1, a^2 + 2, a^2 + 3, a^2 + 4) are all good. Thus, a2a^2 is good and aa odd, so a=1a = 1 or a=2n+1a = 2^n + 1 for n1n \ge 1. If a=1a = 1, then we get the solution:
(1,2,3,4,5) \boxed{(1, 2, 3, 4, 5)}
Now suppose a=2n+1a = 2^n + 1 for n1n \ge 1. Thus, a2+3=(2n+1)2+3a^2 + 3 = (2^n + 1)^2 + 3 is good, so by the claim, we have either n=1n = 1 or n=4n = 4. These give the two solutions:
(9,10,11,12,13)and(289,290,291,292,293) \boxed{(9, 10, 11, 12, 13) \quad \text{and} \quad (289, 290, 291, 292, 293)}

Case 3: Suppose a12(mod4)a_1 \equiv 2 \pmod{4}. Then, a23(mod4)a_2 \equiv 3 \pmod{4} is good, so a2=a2+2a_2 = a^2 + 2 for some odd aa. Thus, the numbers (a2+1,a2+2,a2+3,a2+4,a2+5)(a^2 + 1, a^2 + 2, a^2 + 3, a^2 + 4, a^2 + 5) are all good. Now, a2+52(mod4)a^2 + 5 \equiv 2 \pmod{4} is good, so by the first lemma, we have the following two subcases:

- Subcase 3.1: Suppose a2+5=b2+1a^2 + 5 = b^2 + 1 for odd bb. Then, b2a2=4b^2 - a^2 = 4, so a=0a = 0, which isn't odd.

- Subcase 3.2: Suppose a2+5=b2+2a^2 + 5 = b^2 + 2 for even bb. Then, b2a2=3b^2 - a^2 = 3, so a=1a = 1. This gives the solution:
(2,3,4,5,6) \boxed{(2, 3, 4, 5, 6)}

Case 4: Suppose a13(mod4)a_1 \equiv 3 \pmod{4}. Then, a13(mod4)a_1 \equiv 3 \pmod{4} is good, so a1=a2+2a_1 = a^2 + 2 for some odd aa. Thus, the numbers (a2+2,a2+3,a2+4,a2+5,a2+6)(a^2 + 2, a^2 + 3, a^2 + 4, a^2 + 5, a^2 + 6) are all good. We see that a2+63(mod4)a^2 + 6 \equiv 3 \pmod{4} is good, so a2+6=b2+2a^2 + 6 = b^2 + 2 for odd bb. Thus, b2a2=4b^2 - a^2 = 4, so a=0a = 0, which isn't odd. So there are no solutions here.

We've shown that all the solutions must be in the claimed list, so we're done.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.