Browse · MathNet
PrintFINAL ROUND
Belarus counting and probability
Problem
Alice has sweets. These sweets are distributed among boxes (). Alice chooses some two of these boxes and if the total number of the sweets in these two boxes is even, then she redistributes the sweets so that the numbers of the sweets in these two boxes will be equal. Otherwise she chooses another pair of the boxes and tries to realize the same procedure. Determine all values of for which Alice can equalize the numbers of the sweets in all boxes using this procedure regardless of the initial distribution of the sweets.
Solution
Answer: , where , .
The goal of Alice is to obtain exactly sweets in any box. The number is said to be the distance if is a number of the sweets in the box. Note that the sum of the distances is equal to zero at any moment. Now we see that Alice's goal is to make all distances to be zeros. If there are two boxes with the distances and of the same parity, then Alice can decrease the absolute values of the distances for these boxes if and only if . The necessity of this inequality is obvious. To prove the sufficiency we suppose that :
1) if , then new distances of these boxes satisfy the inequality ;
2) if , then new distances of these boxes are equal to zero.
Therefore, Alice cannot continue decreasing the absolute values of the distances if and only if at some moment either all distances are equal to zeros (and the goal is attained) or distances are even and equal to some , and all other distances are odd and equal to some .
Let (). The sum of all distances is equal to zero at any moment. So, if distances are even and equal to , and all other distances are odd and equal to , then which yields . But the last equality is impossible since is odd and . Therefore, if (), then Alice can equalize the numbers of the sweets in all boxes.
Now let . Then for some positive integer and nonnegative integer . Suppose that there are boxes with the distance and all other boxes with the distance . Note that this distribution of the sweets is possible since the equality holds. Since the numbers and have the different parities, Alice cannot equalize the numbers of the sweets in all boxes.
The goal of Alice is to obtain exactly sweets in any box. The number is said to be the distance if is a number of the sweets in the box. Note that the sum of the distances is equal to zero at any moment. Now we see that Alice's goal is to make all distances to be zeros. If there are two boxes with the distances and of the same parity, then Alice can decrease the absolute values of the distances for these boxes if and only if . The necessity of this inequality is obvious. To prove the sufficiency we suppose that :
1) if , then new distances of these boxes satisfy the inequality ;
2) if , then new distances of these boxes are equal to zero.
Therefore, Alice cannot continue decreasing the absolute values of the distances if and only if at some moment either all distances are equal to zeros (and the goal is attained) or distances are even and equal to some , and all other distances are odd and equal to some .
Let (). The sum of all distances is equal to zero at any moment. So, if distances are even and equal to , and all other distances are odd and equal to , then which yields . But the last equality is impossible since is odd and . Therefore, if (), then Alice can equalize the numbers of the sweets in all boxes.
Now let . Then for some positive integer and nonnegative integer . Suppose that there are boxes with the distance and all other boxes with the distance . Note that this distribution of the sweets is possible since the equality holds. Since the numbers and have the different parities, Alice cannot equalize the numbers of the sweets in all boxes.
Final answer
n = 2^m with m > 1
Techniques
Invariants / monovariantsGames / greedy algorithms