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 "1982 USAMO Problems/Problem 1"

(Created page with "== Problem == In a party with <math>1982</math> persons, among any group of four there is at least one person who knows each of the other three. What is the minimum number of peo...")
 
(→‎Problem)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
In a party with <math>1982</math> persons, among any group of four there is at least one person who knows each of the other three. What is the minimum number of people in the party who know everyone else.
+
In a party with <math>1982</math> people, among any group of four there is at least one person who knows each of the other three. What is the minimum number of people in the party who know everyone else?
  
 
== Solution ==
 
== Solution ==
−
{{solution}}
+
We induct on <math>n</math> to prove that in a party with <math>n</math> people, there must be at least <math>(n-3)</math> people who know everyone else. (Clearly this is achievable by having everyone know everyone else except three people <math>A, B, C</math>, who do not know each other.)
 +
 
 +
Base case: <math>n = 4</math> is obvious.
 +
 
 +
Inductive step: Suppose in a party with <math>k</math> people (with <math>k \ge 4</math>), at least <math>(k-3)</math> people know everyone else. Consider a party with <math>(k+1)</math> people. Take <math>k</math> of the people (leaving another person, <math>A</math>, out) and apply the inductive step to conclude that at least <math>(k-3)</math> people know everyone else in the <math>k</math>-person group, <math>G</math>.
 +
 
 +
Now suppose that everyone in the group <math>G</math> knows each other. Then take <math>3</math> of these people and <math>A</math> to deduce that <math>A</math> knows a person <math>B \in G</math>, which means <math>B</math> knows everyone else. Then apply the inductive step on the remaining <math>k</math> people (excluding <math>B</math>) to find <math>(k-3)</math> people out of them that know everyone else (including <math>B</math>, of course). Then these <math>(k-3)</math> people and <math>B</math>, which enumerate <math>(k-2)</math> people, know everyone else.
 +
 
 +
Suppose that there exist two people <math>B, C \in G</math> who do not know each other. Because <math>k-3 \ge 1</math>, there exist at least one person in <math>G</math>, person <math>D</math>, who knows everyone else in <math>G</math>. Now, take <math>A, B, C, D</math> and observe that because <math>B, C</math> do not know each other, either <math>A</math> or <math>D</math> knows everyone else of <math>A, B, C, D</math> (by the problem condition), so in particular <math>A</math> and <math>D</math> know each other. Then apply the inductive step on the remaining <math>k</math> people (excluding <math>D</math>) to find <math>(k-3)</math> people out of them that know everyone else (including <math>D</math>, of course). Then these <math>(k-3)</math> people and <math>D</math>, which enumerate <math>(k-2)</math> people, know everyone else.
 +
 
 +
This completes the inductive step and thus the proof of this stronger result, which easily implies that at least <math>1982 - 3 = \boxed{1979}</math> people know everyone else.
  
 
== See Also ==
 
== See Also ==
 
{{USAMO box|year=1982|before=First Question|num-a=2}}
 
{{USAMO box|year=1982|before=First Question|num-a=2}}
 +
{{MAA Notice}}
  
 
[[Category:Olympiad Combinatorics Problems]]
 
[[Category:Olympiad Combinatorics Problems]]

Latest revision as of 23:31, 17 January 2016

Problem

In a party with $1982$ people, among any group of four there is at least one person who knows each of the other three. What is the minimum number of people in the party who know everyone else?

Solution

We induct on $n$ to prove that in a party with $n$ people, there must be at least $(n-3)$ people who know everyone else. (Clearly this is achievable by having everyone know everyone else except three people $A, B, C$, who do not know each other.)

Base case: $n = 4$ is obvious.

Inductive step: Suppose in a party with $k$ people (with $k \ge 4$), at least $(k-3)$ people know everyone else. Consider a party with $(k+1)$ people. Take $k$ of the people (leaving another person, $A$, out) and apply the inductive step to conclude that at least $(k-3)$ people know everyone else in the $k$-person group, $G$.

Now suppose that everyone in the group $G$ knows each other. Then take $3$ of these people and $A$ to deduce that $A$ knows a person $B \in G$, which means $B$ knows everyone else. Then apply the inductive step on the remaining $k$ people (excluding $B$) to find $(k-3)$ people out of them that know everyone else (including $B$, of course). Then these $(k-3)$ people and $B$, which enumerate $(k-2)$ people, know everyone else.

Suppose that there exist two people $B, C \in G$ who do not know each other. Because $k-3 \ge 1$, there exist at least one person in $G$, person $D$, who knows everyone else in $G$. Now, take $A, B, C, D$ and observe that because $B, C$ do not know each other, either $A$ or $D$ knows everyone else of $A, B, C, D$ (by the problem condition), so in particular $A$ and $D$ know each other. Then apply the inductive step on the remaining $k$ people (excluding $D$) to find $(k-3)$ people out of them that know everyone else (including $D$, of course). Then these $(k-3)$ people and $D$, which enumerate $(k-2)$ people, know everyone else.

This completes the inductive step and thus the proof of this stronger result, which easily implies that at least $1982 - 3 = \boxed{1979}$ people know everyone else.

See Also

1982 USAMO (Problems • Resources)
Preceded by
First Question 		Followed by
Problem 2
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=1982_USAMO_Problems/Problem_1&oldid=74667"