Difference between revisions of "2005 Indonesia MO Problems/Problem 8"
Rockmanex3 (talk | contribs) (Solution to Problem 8 (credit to Diarmuid) -- meeting contestants) |
(→Solution (credit to Diarmuid)) |
||
| Line 15: | Line 15: | ||
<br> | <br> | ||
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} {3}</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} \geq 3</math>, there must be four contestants that make the same number of new friends, just as Amin claims. | ||
==See Also== | ==See Also== | ||
Revision as of 14:53, 31 December 2019
Problem
There are 
contestants in a mathematics competition. Each contestant gets acquainted with at least 
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)
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 
other contestants. Thus, there are 
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 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 
, 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 
numbers that can be the number of each contestant's new friends. And this seems to disprove Amin's claim because 
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 
, there must be four contestants that make the same number of new friends, just as Amin claims.
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 | ||
