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 == | ||
| − | + | 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: | + | [[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 
vertices and 
edges. The sum of the degrees of the vertices is 
; by the Pigeonhole Principle at least 
vertices have degrees of 
and at most 
vertices have degrees greater than . If we keep deleting edges of vertices with degree greater than (a maximum of such edges), then we are left with at least 
edges, and all of the vertices have degree either 
or . These edges represent the games with distinct players.
See also
| 1989 USAMO (Problems • Resources) | ||
| Preceded by Problem 1 |
Followed by Problem 3 | |
| 1 • 2 • 3 • 4 • 5 | ||
| All USAMO Problems and Solutions | ||
