Page 1 of 1
Tennis League (USAMO 1989)
Posted: Thu Aug 04, 2016 7:48 pm
by Zawadx
The 20 members of a local tennis club have scheduled exactly 14 two-person games among themselves, with each member playing in at least one game. Prove that within this schedule there must be a set of 6 games with 12 distinct players.
Re: Tennis League (USAMO 1989)
Posted: Thu Aug 04, 2016 8:29 pm
by Thanic Nur Samin
Re: Tennis League (USAMO 1989)
Posted: Thu Aug 04, 2016 9:19 pm
by nahin munkar
14 two-person games make $14*2=28$ place to participate. Now,under condition,if all participate in this game just one time,there will be 8 place to play more as there r $20$ players of this tournament . if the players play in those 8 position,there will be 8 games where any player plays more than once. so, If we delete those $8$ games, there r such $(14-8=6)$ games in where one player plays not more than once.So,there must be a set of 6 games with $(6*2)$ or $12$ distinct players within this shedule......(proved)
![Very Happy :D](./images/smilies/icon_e_biggrin.gif)
Re: Tennis League (USAMO 1989)
Posted: Fri Aug 05, 2016 10:42 am
by Zawadx
nahin munkar wrote:14 two-person games make $14*2=28$ place to participate. Now,under condition,if all participate in this game just one time,there will be 8 place to play more as there r $20$ players of this tournament . if the players play in those 8 position,there will be 8 games where any player plays more than once. so, If we delete those $8$ games, there r such $(14-8=6)$ games in where one player plays not more than once.So,there must be a set of 6 games with $(6*2)$ or $12$ distinct players within this shedule......(proved)
![Very Happy :D](./images/smilies/icon_e_biggrin.gif)
Well done.
I've also seen a very cool solution involving counting the edges/vertices (a great tactic if the problem can be rephrased as a graph):