5
$\begingroup$

Problem. In chess tournament each player, from all $n$ players, played one game with every another player. Prove that it is possible to number all players with numbers from $1$ to $n$ in such way that every player has unique number and none of them lost the game against player with number greater by $1$.

My first association was that this tournament can be represented by directed clique and for example edge $\langle a,b \rangle$ means that player with number $a$ won the game against player with number $b$. Then what I need to prove is that vertices in every directed clique with $n$ vertices can be numbered in such way that there in no edge $\langle i+1, \ i \rangle$ for all $i=1,2,...,n-1$.

But it seems very hard, I don't know how to approach.

Or maybe it isn't the problem from graph theory, I don't know.

  • 0
    Well, looks like I *really* misunderstood the problem :)2012-08-29

1 Answers 1

4

You can prove this by induction. The root is - according to taste - a game with just one or two players.

So let's assume we have found a numbering for $n$ players and along comes the $n+1^{st}$ player and plays against every other player.

If he looses against the $n^{th}$ player, we give him the number $n+1$. If he wins against the $n^{th}$ player but also against the $1^{st}$ player, we give hm the number $1$ and move everybody else one up.

So assume he wins against the $n^{th}$ player and looses against the $1^{st}$ player. Then there is a number $k$ such that he wins against player $k$ and looses against player $k-1$. Then we give him the number $k$ and move everybody with a number $>k$ one up.