Difference between revisions of "1989 USAMO Problems/Problem 2"
(if only this yr's USAMO was of this difficulty :)) |
(→Problem) |
||
| (7 intermediate revisions by 6 users not shown) | |||
| Line 1: | Line 1: | ||
== Problem == | == 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 | + | 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 == | ||
| − | + | === Solution 1=== | |
| + | 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 | + | === 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 <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. | ||
| + | |||
| + | === Solution 3=== | ||
| + | Assume the contrary. | ||
| + | |||
| + | Consider the largest set of disjoint edges <math>E</math>. By assumption it has less than <math>6</math> edges, i.e. maximum <math>10</math> vertices. | ||
| + | Call it a vertex set <math>V</math>. | ||
| + | |||
| + | <math>10</math> vertices remain outside <math>V</math> and each has to be attached to at least one edge. | ||
| + | Now, if any two vertices outside <math>V</math> are connected by, say, edge <math>e</math>, we could have included <math>e</math> in <math>E</math> and gotten a larger disjoint set, so - a contradiction. | ||
| + | Therefore the only option would be that all vertices outside <math>V</math> are connected each by one edge to some vertices inside <math>V</math>. That would take <math>10</math> edges, but <math>E</math> already includes <math>5</math> - again a contradiction. | ||
| + | |||
| + | All possibilities yield a contradiction, so our assumption can not be correct. | ||
| + | |||
| + | (Cases when largest set <math>E</math> is smaller than <math>6</math> are equivalent and weaker) | ||
| + | |||
| + | == See Also == | ||
{{USAMO box|year=1989|num-b=1|num-a=3}} | {{USAMO box|year=1989|num-b=1|num-a=3}} | ||
| + | {{MAA Notice}} | ||
| − | [[Category: | + | [[Category:Olympiad Combinatorics Problems]] |
Latest revision as of 00:19, 27 December 2023
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 
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.
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 
games with both slots filled and 
games with only one slot filled, so 
. Since there are only 14 games, 
, so there must be at least 6 games with two distinct members each, and we must have our desired set of 6 games.
Solution 3
Assume the contrary.
Consider the largest set of disjoint edges 
. By assumption it has less than edges, i.e. maximum 
vertices.
Call it a vertex set 
.
vertices remain outside and each has to be attached to at least one edge.
Now, if any two vertices outside are connected by, say, edge 
, we could have included in and gotten a larger disjoint set, so - a contradiction.
Therefore the only option would be that all vertices outside are connected each by one edge to some vertices inside . That would take edges, but already includes 
- again a contradiction.
All possibilities yield a contradiction, so our assumption can not be correct.
(Cases when largest set is smaller than are equivalent and weaker)
See Also
| 1989 USAMO (Problems • Resources) | ||
| 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. 
