Browse · MathNet
PrintVI OBM
Brazil counting and probability
Problem
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 is with 16 different students. But there are only 288 students available, so it can be done for at most days.
We now show explicitly how it can be done for 18 days. Label the students as , where . Now for , take group on day to be , , , , , where all arithmetic is done mod 17. On the final day, take the groups as
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 on day . Take mod 17, then , so is in group . 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 . If , then they are together on the last day. So suppose . Take mod 17 and take mod 17. Then and , so they are together in group on day . But there are only pairs available and we have just shown that each occurs at least once. Hence each occurs at most once, as required.
We now show explicitly how it can be done for 18 days. Label the students as , where . Now for , take group on day to be , , , , , where all arithmetic is done mod 17. On the final day, take the groups as
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 on day . Take mod 17, then , so is in group . 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 . If , then they are together on the last day. So suppose . Take mod 17 and take mod 17. Then and , so they are together in group on day . But there are only pairs available and we have just shown that each occurs at least once. Hence each occurs at most once, as required.
Final answer
18
Techniques
Counting two waysColoring schemes, extremal argumentsInverses mod n