6th Brazil 1984 Problem 2 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?
18 Solution Each day student X is with 16 different students. But there are only 288 students available, so it can be done for at most 288/16 = 18 days. We now show explicitly how it can be done for 18 days. Label the students as (m, n), where 0 ≤ m,n ≤ 16. Now for 0 ≤ d, g ≤ 16, take group g on day d to be (0,g), (1,g+d), (2,g+2d), ... , (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). 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) on day d. Take g = b - ad mod 17, then (a,b) = (a,g+ad), so (a,b) is in group g. 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). If a = A, then they are together on the last day. So suppose a ≠ A. Take d = (b-B)/(a-A) mod 17 and take g = b-ad mod 17. Then (a,b) = (a,g+da) and (A,B) = (A,g+dA), so they are together in group g on day d. But there are only 18 days x 17 groups x (17 x 16)/2 available pairs = 289·288/2 and we have just shown that each occurs at least once. Hence each occurs at most once, as required. 6th Brazil 1984 © John Scholes jscholes@kalva.demon.co.uk 24 Oct 2003 Last corrected/updated 24 Oct 03