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

(if only this yr's USAMO was of this difficulty :))
 
(fix)
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
If there are 14 games with two people each, there must be 28 indistinct players. Since there are just 20 members, at most 8 players could have played in more than one game. That leaves at least <math>14 - 8 = 6</math> games with distinct players.  
+
Consider a graph with <math>20</math> vertices and <math>14</math> edges. The sum of the degrees of the vertices is <math>28</math>; by the [[Pigeonhole Principle]] at least <math>12</math> vertices have degrees of <math>1</math> and at most <math>8</math> vertices have degrees greater than <math>1</math>. If we keep deleting edges of vertices with degree greater than <math>1</math> (a maximum of <math>8</math> such edges), then we are left with at least <math>6</math> edges, and all of the vertices have degree either <math>0</math> or <math>1</math>. These <math>6</math> edges represent the <math>6</math> games with <math>12</math> distinct players.
  
 
== See also ==
 
== See also ==
 
{{USAMO box|year=1989|num-b=1|num-a=3}}
 
{{USAMO box|year=1989|num-b=1|num-a=3}}
  
[[Category:Intermediate Combinatorics Problems]]
+
[[Category:Olympiad Combinatorics Problems]]

Revision as of 21:35, 10 January 2008

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

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.

See also

1989 USAMO (ProblemsResources)
Preceded by
Problem 1
Followed by
Problem 3
1 2 3 4 5
All USAMO Problems and Solutions
Invalid username
Login to AoPS