Competition problem — Combinatorics

Library / /10 of 24

Combinatorics Difficulty 6.5 National olympiad Prove it Argentina

In a math camp there are $2018$ children. The entertainer has $4036$ tokens. There are two tokens with each of the numbers from $1$ to $2018$ ; that is, there are two tokens with number $1$ , two tokens with number $2$ , 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 $2018$ 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 $1$ . Then, if the number of rounds at the beginning is $K$ , the entertainer has to make at least $K-1$ exchanges.

Since every round involves at least $3$ children and $2018 = 3 \cdot 672 + 2$ , the maximum number of rounds at the beginning is $672$ . There can be $670$ rounds with $3$ children each, and $2$ rounds with $4$ children each.

Therefore, the entertainer needs $672 - 1 = 671$ coins to be sure that, for any initial distribution of the tokens, he can obtain a single round by making exchanges.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.