Maths Olympiad Prep

Library / /4 of 5

Combinatorics Difficulty 5.8 AIME, harder Prove it Brazil

Each day 289 students are divided into 17 groups of 17. No two students are ever in the same group more than once. What is the largest number of days that this can be done?

Solution

Each day student XX is with 16 different students. But there are only 288 students available, so it can be done for at most 288/16=18288/16 = 18 days.

We now show explicitly how it can be done for 18 days. Label the students as (m,n)(m, n), where 0m,n160 \le m, n \le 16. Now for 0d,g160 \le d, g \le 16, take group gg on day dd to be (0,g)(0, g), (1,g+d)(1, g+d), (2,g+2d)(2, g+2d), \ldots, (16,g+16d)(16, g+16d), where all arithmetic is done mod 17. On the final day, take the groups as
(0,0),(0,1),,(0,16)(1,0),(1,1),,(1,16)(2,0),(2,1),,(2,16)(16,0),(16,1),,(16,16) \begin{array}{l} (0, 0), (0, 1), \dots, (0, 16) \\ (1, 0), (1, 1), \dots, (1, 16) \\ (2, 0), (2, 1), \dots, (2, 16) \\ \vdots \\ (16, 0), (16, 1), \dots, (16, 16) \end{array}

Note first that for any given day the groups include all the students. That is obvious for the last day. Suppose we want to find the group for student (a,b)(a, b) on day dd. Take g=badg = b - ad mod 17, then (a,b)=(a,g+ad)(a, b) = (a, g + ad), so (a,b)(a, b) is in group gg. Since the groups include just 289 students and each student is included at least once, it follows that each student is included exactly once.

Now consider the pair (a,b),(A,B)(a, b), (A, B). If a=Aa = A, then they are together on the last day. So suppose aAa \ne A. Take d=(bB)(aA)1d = (b - B)(a - A)^{-1} mod 17 and take g=badg = b - ad mod 17. Then (a,b)=(a,g+da)(a, b) = (a, g + da) and (A,B)=(A,g+dA)(A, B) = (A, g + dA), so they are together in group gg on day dd. But there are only 1817(172)=(2892)18 \cdot 17 \cdot \binom{17}{2} = \binom{289}{2} pairs available and we have just shown that each occurs at least once. Hence each occurs at most once, as required.

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.