Difference between revisions of "1989 USAMO Problems/Problem 2"

m (See also)
Line 9: Line 9:
 
Let a slot be a place we can put a member in a game, so there are two slots per game, and 28 slots total.  We begin by filling exactly 20 slots each with a distinct member since each member must play at least one game.  Let there be <math>m</math> games with both slots filled and <math>n</math> games with only one slot filled, so <math>2m+n=20</math>.  Since there are only 14 games, <math>m+n \leq 14 \Longrightarrow 2m+n \leq 14+m \Longleftrightarrow 20 \leq 14+m \Longrightarrow m \geq 6</math>, so there must be at least 6 games with two distinct members each, and we must have our desired set of 6 games.
 
Let a slot be a place we can put a member in a game, so there are two slots per game, and 28 slots total.  We begin by filling exactly 20 slots each with a distinct member since each member must play at least one game.  Let there be <math>m</math> games with both slots filled and <math>n</math> games with only one slot filled, so <math>2m+n=20</math>.  Since there are only 14 games, <math>m+n \leq 14 \Longrightarrow 2m+n \leq 14+m \Longleftrightarrow 20 \leq 14+m \Longrightarrow m \geq 6</math>, so there must be at least 6 games with two distinct members each, and we must have our desired set of 6 games.
  
== See also ==
+
== See Also ==
 
{{USAMO box|year=1989|num-b=1|num-a=3}}
 
{{USAMO box|year=1989|num-b=1|num-a=3}}
 
{{MAA Notice}}
 
{{MAA Notice}}
  
 
[[Category:Olympiad Combinatorics Problems]]
 
[[Category:Olympiad Combinatorics Problems]]

Revision as of 19:11, 18 July 2016

Problem

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

Solution

Solution 1

Consider a graph with $20$ vertices and $14$ edges. The sum of the degrees of the vertices is $28$; by the Pigeonhole Principle at least $12$ vertices have degrees of $1$ and at most $8$ vertices have degrees greater than $1$. If we keep deleting edges of vertices with degree greater than $1$ (a maximum of $8$ such edges), then we are left with at least $6$ edges, and all of the vertices have degree either $0$ or $1$. These $6$ edges represent the $6$ games with $12$ distinct players.

Solution 2

Let a slot be a place we can put a member in a game, so there are two slots per game, and 28 slots total. We begin by filling exactly 20 slots each with a distinct member since each member must play at least one game. Let there be $m$ games with both slots filled and $n$ games with only one slot filled, so $2m+n=20$. Since there are only 14 games, $m+n \leq 14 \Longrightarrow 2m+n \leq 14+m \Longleftrightarrow 20 \leq 14+m \Longrightarrow m \geq 6$, so there must be at least 6 games with two distinct members each, and we must have our desired set of 6 games.

See Also

1989 USAMO (ProblemsResources)
Preceded by
Problem 1
Followed by
Problem 3
1 2 3 4 5
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Invalid username
Login to AoPS