Prove that for all positive integers n, it is possible to organise a round-robin tournament of n football teams in:
a) n-1 rounds if n is even
b)n rounds if n is odd
A round is a set of games in which each team plays one opponent if n is even, and there is only one idle team if n is odd. A round-robin tournament is a tournament in which any pair of teams meet exactly once.
This problem is from the book 'A walk through combinatorics' and is said to be on induction
n=1, n=2, n=3 is trivial
I could prove that if it works for some integer k it would work for 2k in the following way:
if k is even, we could separate two 'groups' of k teams each. We can name the teams t1,t2…tk and tk+1,tk+2,…t2k and have them compete amongst each other in k-1 rounds. Then, we could organise the next k rounds in such a way that for the kth round t1 competes with tk+1 t2 competes with tk+2 and so on. And then for the (k+1)th round, t1 competes with tk+2, t2 competes with tk+3 and tk competes with tk+1 and we could continue in a cyclic manner.
And a similar reasoning when k is odd.
But I have no clue how to proceed further. Any ideas would be appreciated.
Best Answer
Once it works for $2k$ it works for $2k-1$. Delete team $2k$ and give a bye to everyone who should have played them. The change from $n-1$ in case a to $n$ in case b takes care of this. Your induction path is different from the standard monotonic one. If you have the result up to $k$ you have it for all the evens up to $2k$, then you get the odds up to $2k-1$. This still covers all the natural numbers.