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
    I'm not sure that I understand the problem. What about a 3 players tournament where $A$ beats $B$, $B$ beats $C$ and $C$ beats $A$?2012-08-29
  • 0
    @AndreaMori Then any cyclic numbering would do, e.g. $A=1$, $B=2$, $C=3$. Then $1$ didn't loose against $2$ and $2$ didn't loose against $3$.2012-08-29
  • 0
    @SimonMarkett : so the text should be interpreted "each player didn't lose a game with at least one higher numbered opponent"? Reading it, my interpretation was "...didn't lose with all higher numbered opponents", for which my 3-way tournament is an obvious counterexample.2012-08-29
  • 1
    Neither nore: No player lost the game against the player with number _exactly_ $1$ higher.2012-08-29
  • 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.