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 "2005 Indonesia MO Problems/Problem 8"

(→‎Solution 2)
(→‎Solution 2)
 
(5 intermediate revisions by 3 users not shown)
Line 3: Line 3:
 
There are <math>90</math> contestants in a mathematics competition. Each contestant gets acquainted with at least <math>60</math> other contestants. One of the contestants, Amin, state that at least four contestants have the same number of new friends. Prove or disprove his statement.
 
There are <math>90</math> contestants in a mathematics competition. Each contestant gets acquainted with at least <math>60</math> other contestants. One of the contestants, Amin, state that at least four contestants have the same number of new friends. Prove or disprove his statement.
  
−
==Solution (credit to Diarmuid)==
+
==Solution 1 (credit to Diarmuid)==
  
 
In order to disprove Amin's statement, we just need to find one counterexample to Amin's claim.
 
In order to disprove Amin's statement, we just need to find one counterexample to Amin's claim.
Line 16: Line 16:
 
The total number of meets in this scenario is <math>\frac12 \cdot 3 \cdot \frac{(60+89) \cdot 30}{2} = \frac{6705}{2}</math>, which can not happen.  Therefore, there are no valid cases where at most three contestants have the same number of new friends, so Amin is correct.
 
The total number of meets in this scenario is <math>\frac12 \cdot 3 \cdot \frac{(60+89) \cdot 30}{2} = \frac{6705}{2}</math>, which can not happen.  Therefore, there are no valid cases where at most three contestants have the same number of new friends, so Amin is correct.
  
 +
==Solution 2==
 +
 +
For every contestant, he or she already knows 60 people, so he or she can at most make 29 new friends (excluding oneself). The least number of friends one can make is obviously 0, so there seems to be <math>29 - 0 + 1 = 30</math> numbers that can be the number of each contestant's new friends. And this seems to disprove Amin's claim because <math>\frac{90}{30}</math> is exactly equal to 3.
 +
 +
However, it's important to note that number 0 and number 29 cannot be reached simultaneously, because if one knows 29 new people, he or she must make friends with everyone, so 0 cannot be achieved. Therefore, there is at most 29 numbers possible. Since <math>\frac{90}{29} > 3</math>, there must be four contestants that make the same number of new friends, just as Amin claims.
  
−
==Solution 2==
+
==Solution 3 (credit to dskull16)==
  
−
For every contestant, he or she already knows 60 people, so he or she can at most make 29 new friends (excluding oneself). The least number of friends one can make is obviously 0, so there seems to be <math>29 - 0 + 1 = 30</math> numbers that can be the number of each contestant's new friends. And this seems to disprove Amin's claim because <math>\frac{90}{3}</math> is exactly equal to 3.
+
We can represent this problem by a graph where the nodes are the 90 contestants and an edge between two nodes represents an acquaintance being made. It is worth noting that this graph is simple meaning that double connections and self connections are not allowed and therefore that the maximum degree of any given vertex is 89.
  
−
However, it's important to note that number 0 and number 29 cannot be reached simultaneously, because if one knows 29 new people, he or she must make friends with everyone, so 0 cannot be achieved. Therefore, there is at most 29 numbers possible.  
+
<br>
 +
In the limiting case, the degree sequence of the graph is <math>60, 60, 60,
 +
61, 61, 61 ... 89, 89, 89</math>. Note that we cannot change any of these degrees as 60 is a lower bound and 89 is an upper bound and as such, any alteration would give a node with a degree of 4. By the fundamental theorem of graph theory, the sum of all the degrees in a graph is precisely equal to twice the number of edges. This implies that the above degree sum must be an even number.  
  
−
Since <math>\frac{90}{29} \geq 3</math>, there must be four contestants that make the same number of new friends, just as Amin claims.
+
<br>
 +
Given that there are 15 odd numbers between 60 and 89 inclusive, this shows that the sum is in fact odd and hence constructing such a graph is not possible meaning that Amin is correct.
  
 
==See Also==
 
==See Also==

Latest revision as of 18:58, 3 February 2024

Problem

There are $90$ contestants in a mathematics competition. Each contestant gets acquainted with at least $60$ other contestants. One of the contestants, Amin, state that at least four contestants have the same number of new friends. Prove or disprove his statement.

Solution 1 (credit to Diarmuid)

In order to disprove Amin's statement, we just need to find one counterexample to Amin's claim.


Note that each person can meet up to $89$ other contestants. Thus, there are $89 - 60 + 1 = 30$ numbers that can be the number of contestants one meets.


For each number of contestants one meets, there can be at most 3 contestants (for Amin's claim to be disproven), so there can be a total of at most $90$ contestants (which is the same as the number at the competition). So we only need to check whether it's possible for that one case to happen.


The total number of meets in this scenario is $\frac12 \cdot 3 \cdot \frac{(60+89) \cdot 30}{2} = \frac{6705}{2}$, which can not happen. Therefore, there are no valid cases where at most three contestants have the same number of new friends, so Amin is correct.

Solution 2

For every contestant, he or she already knows 60 people, so he or she can at most make 29 new friends (excluding oneself). The least number of friends one can make is obviously 0, so there seems to be $29 - 0 + 1 = 30$ numbers that can be the number of each contestant's new friends. And this seems to disprove Amin's claim because $\frac{90}{30}$ is exactly equal to 3.

However, it's important to note that number 0 and number 29 cannot be reached simultaneously, because if one knows 29 new people, he or she must make friends with everyone, so 0 cannot be achieved. Therefore, there is at most 29 numbers possible. Since $\frac{90}{29} > 3$, there must be four contestants that make the same number of new friends, just as Amin claims.

Solution 3 (credit to dskull16)

We can represent this problem by a graph where the nodes are the 90 contestants and an edge between two nodes represents an acquaintance being made. It is worth noting that this graph is simple meaning that double connections and self connections are not allowed and therefore that the maximum degree of any given vertex is 89.


In the limiting case, the degree sequence of the graph is $60, 60, 60, 61, 61, 61 ... 89, 89, 89$. Note that we cannot change any of these degrees as 60 is a lower bound and 89 is an upper bound and as such, any alteration would give a node with a degree of 4. By the fundamental theorem of graph theory, the sum of all the degrees in a graph is precisely equal to twice the number of edges. This implies that the above degree sum must be an even number.


Given that there are 15 odd numbers between 60 and 89 inclusive, this shows that the sum is in fact odd and hence constructing such a graph is not possible meaning that Amin is correct.

See Also

2005 Indonesia MO (Problems)
Preceded by
Problem 7 		1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 Followed by
Last Problem
All Indonesia MO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2005_Indonesia_MO_Problems/Problem_8&oldid=214414"