Maths Olympiad Prep

Library / /17 of 23

Number theory Difficulty 5.5 AIME, harder Find the answer United States

Let m5m \ge 5 be an odd integer, and let D(m)D(m) denote the number of quadruples (a1,a2,a3,a4)(a_1, a_2, a_3, a_4) of distinct integers with 1aim1 \le a_i \le m for all ii such that mm divides a1+a2+a3+a4a_1 + a_2 + a_3 + a_4. There is a polynomial q(x)=c3x3+c2x2+c1x+c0q(x) = c_3x^3 + c_2x^2 + c_1x + c_0 such that D(m)=q(m)D(m) = q(m) for all odd integers m5m \ge 5. What is c1c_1?

Pick one

Solution

Let s(m,r)s(m,r) denote the number of quadruples (a1,a2,a3,a4)(a_1, a_2, a_3, a_4) of distinct residue classes modulo mm such that a1+a2+a3+a4r(modm)a_1 + a_2 + a_3 + a_4 \equiv r \pmod{m}. Because the total number of quadruples of distinct residue classes is m(m1)(m2)(m3)m(m-1)(m-2)(m-3), it follows that
r=1ms(m,r)=m(m1)(m2)(m3). \sum_{r=1}^{m} s(m, r) = m(m-1)(m-2)(m-3).
Note that the pairing (a1,a2,a3,a4)(a1+1,a2+1,a3+1,a4+1)(a_1, a_2, a_3, a_4) \longleftrightarrow (a_1+1, a_2+1, a_3+1, a_4+1) provides a one-to-one correspondence between quadruples of distinct residue classes that sum to rr and quadruples of distinct residue classes that sum to r+4r+4. Hence s(m,r)=s(m,r+4)s(m, r) = s(m, r+4), so
s(m,r)=s(m,r+4)=s(m,r+8)= s(m, r) = s(m, r+4) = s(m, r+8) = \dots
Now gcd(4,m)=1\gcd(4, m) = 1 because mm is odd, so the numbers r,r+4,r+8,,r+4(m1)r, r+4, r+8, \dots, r+4(m-1) form a complete residue system modulo mm. Thus the values s(m,r)s(m, r) are all equal. From the displayed summation above it follows that
s(m,r)=(m1)(m2)(m3)=m36m2+11m6 s(m, r) = (m-1)(m-2)(m-3) = m^3 - 6m^2 + 11m - 6
for all rr. Because D(m)=s(m,0)D(m) = s(m, 0), it follows that the required polynomial is q(x)=x36x2+11x6q(x) = x^3 - 6x^2 + 11x - 6, and c1=11c_1 = 11.

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.