Maths Olympiad Prep

Library / /10 of 15

, 2021

Algebra Difficulty 5.1 AIME, harder Find the answer United States

For each integer n2n \ge 2, let SnS_n be the sum of all products jkjk, where jj and kk are integers and 1j<kn1 \le j < k \le n. What is the sum of the 10 least values of nn such that SnS_n is divisible by 3?

Pick one

Solution

Un=(1+2+3++(n1))n=(n1)n22. U_n = (1 + 2 + 3 + \dots + (n-1)) \cdot n = \frac{(n-1)n^2}{2}.
Then Sn=Sn1+UnS_n = S_{n-1} + U_n for n3n \ge 3. Note that UnU_n is divisible by 3 if n0 or 1(mod3)n \equiv 0 \text{ or } 1 \pmod 3; and if n2(mod3)n \equiv 2 \pmod 3, then (n1)n21(mod3)(n-1)n^2 \equiv 1 \pmod 3 and is even, so Un2(mod3)U_n \equiv 2 \pmod 3. Hence Sn+3Sn+2(mod3)S_{n+3} \equiv S_n + 2 \pmod 3 for n2n \ge 2. It is readily verified that S2S3S42(mod3)S_2 \equiv S_3 \equiv S_4 \equiv 2 \pmod 3, so S5S6S71(mod3)S_5 \equiv S_6 \equiv S_7 \equiv 1 \pmod 3 and S8S9S100(mod3)S_8 \equiv S_9 \equiv S_{10} \equiv 0 \pmod 3, and it follows that SnS_n is divisible by 3 if and only if n0 or ±1(mod9)n \equiv 0 \text{ or } \pm 1 \pmod 9. Thus the sum of the 10 least values of nn that satisfy the required condition is
8+9+10+17+18+19+26+27+28+35=197. 8 + 9 + 10 + 17 + 18 + 19 + 26 + 27 + 28 + 35 = 197.

The sum of the products jkjk as jj and kk run independently from 1 to nn is
(1+2++n)2=(n(n+1)2)2. (1 + 2 + \dots + n)^2 = \left(\frac{n(n+1)}{2}\right)^2.
To eliminate the cases in which j=kj = k, subtract
12+22++n2=n(n+1)(2n+1)6. 1^2 + 2^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}.
Thus
1jn1knjkjk=n2(n+1)24n(n+1)(2n+1)6=(n1)n(n+1)(3n+2)12. \sum_{\substack{1 \le j \le n \\ 1 \le k \le n \\ j \ne k}} jk = \frac{n^2(n+1)^2}{4} - \frac{n(n+1)(2n+1)}{6} = \frac{(n-1)n(n+1)(3n+2)}{12}.
For a given pair j,kj, k with jkj \ne k either j<kj < k or j>kj > k, but their product is the same in either order. To impose the condition j<kj < k, it suffices to divide by 2. Thus
Sn=(n1)n(n+1)(3n+2)24. S_n = \frac{(n-1)n(n+1)(3n+2)}{24}.
There is one factor of 3 in the denominator. For any nn, exactly one of n+1,n,n1n+1, n, n-1 is divisible by 3, and 3n+23n+2 is not divisible by 3. In order that SnS_n be divisible by 3 it is necessary and sufficient that the factor that is divisible by 3 should in fact be divisible by 9. That is, n0 or ±1(mod9)n \equiv 0 \text{ or } \pm 1 \pmod 9, and the answer can be calculated as above.

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.