Maths Olympiad Prep

Library / /232 of 462

Combinatorics Difficulty 5.8 AIME, harder Prove it Ireland

In how many ways can 20212021 be expressed as a sum of four positive integers none of which is a multiple of 33? Sums with different orders count as distinct.

Solution

Let the four integers be n1,n2,n3,n4n_1, n_2, n_3, n_4 and write them as
nj=3xjrjxj1,rj=1 or 2. n_j = 3x_j - r_j \quad x_j \ge 1, r_j = 1 \text{ or } 2.
Without any further constraint, there are 1616 possible combinations of values 11 and 22 for the rjr_j. However, as 20212(mod3)2021 \equiv 2 \pmod 3, we must have
r1+r2+r3+r421(mod3), r_1 + r_2 + r_3 + r_4 \equiv -2 \equiv 1 \pmod 3,
and given the range of the rjr_j this implies r1+r2+r3+r4=4r_1 + r_2 + r_3 + r_4 = 4 or 77. The first of these has one case, the second has four:

r1r_1r2r_2r3r_3r4r_4r1+r2+r3+r4r_1 + r_2 + r_3 + r_4
11114
12227
21227
22127
22217

Let s=x1+x2+x3+x4s = x_1+x_2+x_3+x_4, then 2021=n1+n2+n3+n4=3s+(r1+r2+r3+r4)2021 = n_1+n_2+n_3+n_4 = 3s+(r_1+r_2+r_3+r_4) and
s=2021+r1+r2+r3+r43=675 or 676. s = \frac{2021 + r_1 + r_2 + r_3 + r_4}{3} = 675 \text{ or } 676.
The number of solutions to the original problem is equal to the number of solutions to x1+x2+x3+x4=675x_1+x_2+x_3+x_4 = 675 plus four times the number of solutions to x1+x2+x3+x4=676x_1+x_2+x_3+x_4 = 676. By considering the numbers {x1,x1+x2,x1+x2+x3}\{x_1, x_1+x_2, x_1+x_2+x_3\} as a subset of {1,2,3,,s1}\{1, 2, 3, \dots, s-1\} we conclude that the number of solutions (x1,x2,x3,x4)(x_1, x_2, x_3, x_4) to x1+x2+x3+x4=sx_1 + x_2 + x_3 + x_4 = s is
(s13). \binom{s-1}{3}.
Therefore, the number of solutions to the original problem is

(6743)+4(6753)\binom{674}{3} + 4\binom{675}{3} = 674 673\cdot 673 \cdot 562 = 254\,924\,324.

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.