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.

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|improve this question
add comment

2 Answers

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|improve this answer
add comment

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|improve this answer
add comment

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.