Browse · MathNet
PrintXXVII Olimpiada Matemática Rioplatense
Argentina counting and probability
Problem
In a math camp there are children. The entertainer has tokens. There are two tokens with each of the numbers from to ; that is, there are two tokens with number , two tokens with number , and so on.
Two tokens with different numbers are given to every child. There cannot be two children receiving the same two numbers.
The children are arranged so that the following condition is satisfied: each child holds a hand with each of the two children sharing a number with him or her.
An exchange consists in asking two children to exchange one of their tokens and to rearrange so that the previous condition is still satisfied.
If the children have not end in a round, the entertainer can make exchanges to get them form a single big round. But every time he makes an exchange, he must deposit a coin in the money box.
What is the minimum number of coins that the entertainer needs to be sure that, for any initial distribution of the tokens, he can obtain a big round by making exchanges?
Two tokens with different numbers are given to every child. There cannot be two children receiving the same two numbers.
The children are arranged so that the following condition is satisfied: each child holds a hand with each of the two children sharing a number with him or her.
An exchange consists in asking two children to exchange one of their tokens and to rearrange so that the previous condition is still satisfied.
If the children have not end in a round, the entertainer can make exchanges to get them form a single big round. But every time he makes an exchange, he must deposit a coin in the money box.
What is the minimum number of coins that the entertainer needs to be sure that, for any initial distribution of the tokens, he can obtain a big round by making exchanges?
Solution
Since every child holds hands with the two children sharing a number with him or her, when the children are arranged, they form several rounds (possibly more than one).
If the entertainer makes an exchange between two children in different rounds, the two rounds join in a single round. An exchange between two children in the same round either turns the round into two separate rounds or makes a reordering of the children in the round. So, after every exchange, the number of rounds decreases at most by . Then, if the number of rounds at the beginning is , the entertainer has to make at least exchanges.
Since every round involves at least children and , the maximum number of rounds at the beginning is . There can be rounds with children each, and rounds with children each.
Therefore, the entertainer needs coins to be sure that, for any initial distribution of the tokens, he can obtain a single round by making exchanges.
If the entertainer makes an exchange between two children in different rounds, the two rounds join in a single round. An exchange between two children in the same round either turns the round into two separate rounds or makes a reordering of the children in the round. So, after every exchange, the number of rounds decreases at most by . Then, if the number of rounds at the beginning is , the entertainer has to make at least exchanges.
Since every round involves at least children and , the maximum number of rounds at the beginning is . There can be rounds with children each, and rounds with children each.
Therefore, the entertainer needs coins to be sure that, for any initial distribution of the tokens, he can obtain a single round by making exchanges.
Final answer
671
Techniques
Invariants / monovariantsColoring schemes, extremal arguments