Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Here is a combinatorics problem having to do with graph-theory

Ten players participate at a chess tournament. Eleven games have already been played. Prove that there is a player who has played at least 3 games.

share|cite|improve this question

Say player $i$ has played $r_i$ games. Since $11$ games have been played $$r_1+r_2+\ldots +r_{10}=22.$$ If we suppose that each player has played at most 2 games then $$r_1+r_2+\ldots +r_{10}\leq 20$$ giving us a contradiction.

share|cite|improve this answer

Not exacly Graph Theory, more Pigeonhole Principle. Every time a player plays a game, she makes an X on the blackboard. Since $11$ games have been played, and each game involves $2$ people, there are $22$ X on the blackboard. So one player must have made $3$ or more X. This is because if all players had made $2$ or fewer X, there would be at most $20$ X on the board.

Or else think in terms of money. Every time a player plays, she puts $1$ dollar into the beer fund. Since $11$ games have been played, there are $22$ dollars in the beer fund. So one player at least must have put in $3$ dollars or more, that is, played $3$ or more games.

share|cite|improve this answer

Your Answer


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.