13th CanMO 1981 Problem 5 11 groups perform at a festival. Each day any groups not performing watch the others (but groups performing that day do not watch the others). What is the smallest number of days for which the festival can last if every group watches every other group at least once during the festival? Solution
: 6 days. It is not obvious how to approach this. Consider the case of n groups. It is easy to make do with n days. For example, on day i, group i performs and the others watch. Or vice versa. For n = 3, 3 days are necessary, 1 watching 2, 2 watching 3 and 3 watching 1 must occur on separate days. It is not quite as obvious that 4 days are needed for n = 4. Suppose three days suffice. Then on some day two groups perform. Wlog 1 and 2 perform on day 1. Then we need two more days for 1 to watch 2 and 2 to watch 1. So assume 1 watches 2 on day 2 and 2 watches 1 on day 3. The only day 1 is in the audience is day 2, so 3 and 4 must perform on day 2. Similarly, 2 is only in the audience on day 3, so 3 and 4 must perform on day 3. But now 3 and 4 must be in the audience on day 1 in order to watch 1 and 2. That means they cannot watch each other. So we need 4 days. However, 4 days suffice for n = 6. For example: 1 2 3 watch 4 5 6 1 4 5 watch 2 3 6 2 4 6 watch 1 3 5 3 5 6 watch 1 2 4 Note that if m days suffice for n, then they also suffice for n-1 - just delete one group from the schedule. So 4 days also suffice for 5. They must be necessary, because otherwise we could do 4 groups in 3 days. We can now do 12 groups in 6 days (and hence also 11 groups in 6 days): 1 2 3 A B C watch 4 5 6 D E F 1 4 5 A D E watch 2 3 6 B C F 2 4 6 B D F watch 1 3 5 A C E 3 5 6 C E F watch 1 2 4 A B D 1 2 3 4 5 6 watch A B C D E F A B C D E F watch 1 2 3 4 5 6 Note that this is general. If m days suffice for n groups, then m+2 suffice for 2n groups. With a slight variant we can do 10 groups in 5 days: 1 2 3 A B C watch 4 5 6 D 1 4 5 A B D watch 2 3 6 C2 4 6 A C D watch 1 3 5 B 3 5 6 B C D watch 1 2 4 A 1 2 3 4 5 6 watch A B C D So to finish off we have to show that 5 days are not sufficient for 11 groups. If we also show that 4 are not sufficient for 7 groups, then we have dealt with all cases up to n = 12. Consider n = 7. Suppose we only need 4 days. If a group only performs once, then the other 6 groups must watch that day. So none of them watch each other. So they need at least 4 days to watch each other and only 3 are available. So each group must perform at least twice. But that means on some day at least 4 groups perform (4 days x 3 groups < 7 groups x 2 performances). On that day none of the 4 can watch each other. But they need 4 days to watch each other. So 7 groups need at least 5 days. Consider n = 11. Suppose we only need 5 days. Each day at least 6 groups are watching or at least 6 groups are performing. So there must be three days with at least 6 groups watching or three days with at least 6 groups performing. But that means that there are 4 groups which all perform on 2 days or which all watch on 2 days. In either case, they need a further 4 days to watch each other. Contradiction. [The claim that if 6 groups watch on three days, then we can find a particular set of 4 which watch on two of the three days is justified as follows. If only 3 watch on more than one day, then that leaves 8 who watch on just one day. So there is a day when at most 2 of the 8 watch. But then on that day at most 2 + 3 can watch, whereas 6 are supposed to.] Summary: n 3 4 5 6 7 8 9 10 11 12 days 3 4 4 4 5 5 5 5 6 6 13th CanMO 1981 © John Scholes jscholes@kalva.demon.co.uk 21 June 2002