Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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$? –  Andrea Mori Aug 29 '12 at 9:44
    
@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$. –  Simon Markett Aug 29 '12 at 9:55
    
@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. –  Andrea Mori Aug 29 '12 at 10:01
1  
Neither nore: No player lost the game against the player with number exactly $1$ higher. –  Simon Markett Aug 29 '12 at 10:03
    
Well, looks like I really misunderstood the problem :) –  Andrea Mori Aug 29 '12 at 10:16

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.