Skip to main content
OlympiadHQ

Browse · MathNet

Print

Croatian Junior Mathematical Olympiad

Croatia counting and probability

Problem

One hundred people attended the party, some of whom were previously acquainted. All acquaintances were mutual and no new were made during the party. A gong rang times during the party. After the first sounding of the gong, all the people not acquainted with anyone left the party. After the second sounding of the gong, all the people with exactly one acquaintance (among the remaining people) left. It continued all the way, meaning that after the th sounding of the gong, all the people acquainted with exactly remaining people left the party (). At the end of the party, there were people still present. Find all possible values of .
Solution
We show that can be . The following contains the description of a situation in which exactly people are present after the last chime (for ): For , we can divide all the people at the party into two groups, A and B. Let A contain people and assume every one of them is acquainted with all the other people at the party. Let B contain the remaining people, none of whom are acquainted amongst themselves, but all of whom are acquainted with all the people in group A (thus, every person in group B has acquaintances). All the people from group B will obviously leave the party after the sounding of the gong. After that, only people from group A will remain, and each of them will have exactly acquaintances. As the gong has already been sounded times, this means none of them will leave until the end of the party. The value is attained, for example, when all the party-goers know each other (so they all leave after the th chime). A simple observation shows that at least one person must leave at some moment: this is the person with the fewest acquaintances. This implies that cannot be attained. Finally, let us prove that is not possible. Assume the contrary, i.e. that exactly one person will leave the party before it ends; call this person . As the first one to leave, this is obviously the person with the fewest acquaintances. Since none of the remaining people leave after , we conclude that all of them must be acquainted with - if another person is not acquainted with , then the number of people they know would not change with leaving, so they would have to leave at some point as well. This shows that has acquaintances, which contradicts the assumption that has the fewest acquaintances.
Final answer
0, 1, 2, ..., 98

Techniques

Graph TheoryInvariants / monovariantsColoring schemes, extremal arguments