In a football season, even number $n$ of teams plays a simple series, i.e. each team plays once against each other team. Show that ona can group the series into $n-1$ rounds such that in every round every team plays exactly one match.
Problem
Source: Finnish Mathematics Competition 2010, Final Round, Problem 4
Tags: modular arithmetic, induction, combinatorics unsolved, combinatorics
22.11.2011 19:54
Let us enumerate the teams by integers $1,\ldots,n$. Consider the $i$th round, $1\leq i\leq n-1$. Suppose that team $x$ opponent is $y$ such that $x+y+i$ is divisible by $n-1$ and $1\leq y<n$. If $x+x+i=2x+i$ is divisible by $n-1$, $x$'s opponent will be $n$. We have to show that every team plays on every round and every team plays against any other team. Let us show that $n$ plays on every round. If $2x_1+i$ and $2x_2+i$ have the same remainder mod $n-1$ then $2(x_1-x_2)$ is a multiple of odd number $n-1$. But as $|x_1-x_2|<(n-1)-1<n-1$, we have $x_1=x_2$. Remainders are $n-1$ different numbers from the set $\{0,1,\ldots,n-2\}$ so exactly one of these is zero. So $n$ has always an opponent. Similarly, is $2x+i$ is not divisible by $n-1$ there is exactly one $y\ne x$ such that $x+y+i$ is a multiple of $n-1$. So every team has an opponent on the round $i$ and $x$ has an opponent $y$ then $y$ has an opponent $x$. Finally, let us show that every pair of teams will be played. If $x\ne y$ then the remainders of $x+y+1, x+y+2,\ldots,x+y+(n-1)$ are different mod $n-1$. Thus there is $i\in \{1,\ldots,n\}$ such that $x+y+i\equiv 0 \pmod n-1$. Therefore $x$ and $y$ plays against themselves on round $i$ and no other round. Also, exactly one of the numbers $2x+1,\ldots,2x+(n-1)$ is a multiple of $n-1$, say $2x+k$. Now $x$ and $n$ plays against each others on round $k$.
23.11.2011 02:31
A more graphic proof. Remove for the moment team number $n$. Put the others as vertices of a regular $(n-1)$-gon. Have play in round $k$, with $1\leq k \leq n-1$, matches between those teams at the ends of the side opposite vertex $k$, and between those teams at the ends of any diagonal parallel to the side opposite vertex $k$. The only team thus not matched is team $k$; have it play against team $n$.
23.11.2011 16:39
@mavropnevma: Nice proof.
23.11.2011 16:42
Can you please show your proof using induction?
24.11.2011 09:43
I was mistaken. It had a flaw.