Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(fix)
(→‎Problem)
 
(6 intermediate revisions by 5 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 ==
−
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.
+
=== 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 also ==
+
=== 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:Olympiad Combinatorics Problems]]
 
[[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 $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.

Solution 3

Assume the contrary.

Consider the largest set of disjoint edges $E$. By assumption it has less than $6$ edges, i.e. maximum $10$ vertices. Call it a vertex set $V$.

$10$ vertices remain outside $V$ and each has to be attached to at least one edge. Now, if any two vertices outside $V$ are connected by, say, edge $e$, we could have included $e$ in $E$ and gotten a larger disjoint set, so - a contradiction. Therefore the only option would be that all vertices outside $V$ are connected each by one edge to some vertices inside $V$. That would take $10$ edges, but $E$ already includes $5$ - again a contradiction.

All possibilities yield a contradiction, so our assumption can not be correct.

(Cases when largest set $E$ is smaller than $6$ 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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1989_USAMO_Problems/Problem_2&oldid=208486"