, 2009

Solution:

A given pair must play with three other pairs and these plays must be in different days, so at least three days are needed. Suppose that three days suffice. Let the pair $AB$ play against $CD$ on day $x$. Then $AB-DE$ and $CD-BE$ cannot play on day $x$. Then one of the other two plays of $DE$ (with $AC$ and $BC$) must be on day $x$. Similarly, one of the plays of $BE$ with $AC$ or $AD$ must be on day $x$. Thus, two of the plays in the chain $BC-DE-AC-BE-AD$ are on day $x$ (more than two among these cannot be on one day).

Consider the chain $AB-CD-EA-BD-CE-AB$. At least three days are needed for playing all the matches within it. For each of these days we conclude (as above) that there are exactly two of the plays in the chain $BC-DE-AC-BE-AD-BC$ on that day. This is impossible, as this chain consists of five plays.

It remains to show that four days will suffice:

Day 1: $AB-CD$, $AC-DE$, $AD-CE$, $AE-BC$

Day 2: $AB-DE$, $AC-BD$, $AD-BC$, $BE-CD$

Day 3: $AB-CE$, $AD-BE$, $AE-BD$, $BC-DE$

Day 4: $AC-BE$, $AE-CD$, $BD-CE$.

Solution:

There are 10 pairs. Each of them plays 3 games, so the tournament needs to last at least 3 days. Assume the tournament could finish in 3 days. Then every pair must play one game on each day. There are 15 games to be played, so you must have 5 games on each day. Call "Day 1" the day $AB$ plays against $CD$, "Day 2" the day $AB$ plays against $DE$ and "Day 3" the day $AB$ plays against $CE$. Let us examine the other possible games on Day 1. $CE$ can't play $AB$, so it must play either $AD$ or $BD$. $DE$ can't play $AB$, so it must play $AC$ or $BC$. Similarly, $AE$ can't play $CD$, so it must play $BC$ or $BD$, and $BE$ must play either $AC$ or $AD$. We obtain the following circular diagram in which exactly every other game has to take place on Day 1, either the red ones or the blue ones:

Similar reasoning leads us to the following diagram for Day 2. Here again, either all the red matches have to take place, or all the blue matches have to take place on Day 2.

One can't have the blue matches on both Day 1 and Day 2 because $AD-BE$ would repeat itself.
We can't have the red matches on both days as this would repeat the match $BD-CE$.
We can not have the blue matches on Day 1 and the red matches on Day 2 because this would repeat the game $AC-BE$. Finally, choosing the red matches on Day 1 and the blue ones on Day 2 won't work either as the game $AE-BC$ would repeat itself.

In conclusion, the tournament has to last at least four days. An example of how it could be organized in four days is given in the previous solution.