IBM Research | Ponder This | November 2011 solutions

# Ponder This

## November 2011

<<October November December>>

First, we prove that no solution can exist without violating at least once either condition (a) or condition (b).

If such a tournament takes place, it's easy to see that the same three teams will have to referee together, splitting the nine teams into three triplets.

Let's call them groups A, B and C.

Any game between a team from group B and a team from group C must take place when a group A team is refereeing.

In each round when group A teams are refereeing, the number of BB games (i.e., both teams from the B group) is the same as the number of CC games.

Therefore the number of BC games is odd (3-BB-CC). There are nine BC games and four A-refereeing rounds, but 9 cannot be expressed as a sum of four odd numbers, so that proves that we cannot fully fulfill conditions (a) and (b).

Allowing for a single violation is enough. For example, the solution below fulfills condition (a) and violates (b) only once when team 7 referees in the 11th and 9th rounds.

4 9 (1)   5 7 (2)   6 8 (3)
1 7 (4)   2 8 (5)   3 9 (6)
1 3 (7)   2 4 (8)   5 6 (9)
6 9 (2)   7 8 (3)   4 5 (1)
2 9 (5)   3 7 (6)   1 8 (4)
2 5 (8)   3 6 (9)   1 4 (7)
7 9 (3)   4 6 (1)   5 8 (2)
3 8 (6)   1 9 (4)   2 7 (5)
3 4 (9)   1 5 (7)   2 6 (8)
4 8 (1)   5 9 (2)   6 7 (3)
1 6 (4)   2 3 (5)   8 9 (7)
1 2 (8)   3 5 (9)   4 7 (6)

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com