Maths Olympiad Prep

Library / /35 of 86

Number theory Difficulty 5.7 AIME, harder Prove it Estonia

Show that there exist infinitely many positive integers nn such that the integers 1,2,3,,2n1, 2, 3, \dots, 2n can be split into pairs such that the sum of the products of the pairs is divisible by 2n2n.

Solutions — 3

Solution 1

For each prime pp we can split the numbers 1,2,3,,2p1, 2, 3, \dots, 2p into the pairs (1,p+1),(2,p+2),,(p,2p)(1, p+1), (2, p+2), \dots, (p, 2p). The products of the pairs are congruent to 12,22,,(p1)2,p21^2, 2^2, \dots, (p-1)^2, p^2 modulo pp, so the sum of the products is congruent to 12+22++p2=p(p+1)(2p+1)61^2 + 2^2 + \dots + p^2 = \frac{p(p+1)(2p+1)}{6}. So for p>3p > 3, pp divides 12+22++p21^2 + 2^2 + \dots + p^2, as it doesn't divide the denominator. Also, in each pair one of the numbers is even, so the product is even. Hence the sum of the products is divisible by 22 and therefore also by 2p2p, as desired.

Solution 2

We use the identity 12+34++(2n1)2n=n(n+1)(4n1)31 \cdot 2 + 3 \cdot 4 + \dots + (2n-1) \cdot 2n = \frac{n(n+1)(4n-1)}{3}.

If nn is not divisible by 22 or 33, then 2nn(n+1)(4n1)32n \mid \frac{n(n+1)(4n-1)}{3}, since 2n+12 \mid n+1 and either 3n+13 \mid n+1 or 34n13 \mid 4n-1, depending on whether n1(mod3)n \equiv -1 \pmod 3 or n1(mod3)n \equiv 1 \pmod 3. Therefore splitting the numbers 1,2,3,,2n1, 2, 3, \dots, 2n into the pairs (1,2),(3,4),,(2n1,2n)(1, 2), (3, 4), \dots, (2n-1, 2n) works for infinitely many nn.

Solution 3

For each prime pp we can split the numbers 1,2,3,,2p1, 2, 3, \dots, 2p into the pairs (1,p+1),(2,p+2),,(p,2p)(1, p+1), (2, p+2), \dots, (p, 2p). The products of the pairs are congruent to 12,22,,(p1)2,p21^2, 2^2, \dots, (p-1)^2, p^2 modulo pp.
Let p1(mod4)p \equiv 1 \pmod 4 (by Dirichlet's theorem, there are infinitely many such primes), then there exists an integer aa such that a21(modp)a^2 \equiv -1 \pmod p. If p>2p > 2, then clearly a≢1,1(modp)a \not\equiv 1, -1 \pmod p. Then for all i=1,2,,p1i = 1, 2, \dots, p-1 the numbers i,ai,a2i,a3ii, ai, a^2i, a^3i give different remainders modulo pp, whereas a4ii(modp)a^4i \equiv i \pmod p. So the remainders 1,2,,p11, 2, \dots, p-1 are split into 4-cycles. The sum of squares of each 4-cycle is divisible by pp, as i2+(ai)2=(1+a2)i2(11)i2=0(modp)i^2 + (ai)^2 = (1 + a^2)i^2 \equiv (1 - 1)i^2 = 0 \pmod p. So the sum 12+22++(p1)21^2 + 2^2 + \dots + (p-1)^2 is divisible by pp. Adding also the final term p2p^2, the divisibility will still hold. Also, in each pair one of the numbers is even, so the product is even. Therefore the sum of the products is divisible by 22 and therefore also by 2p2p, as desired.

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 and solution reproduced as published; topic and difficulty added by this site.