Maths Olympiad Prep

Library / /18 of 18

Combinatorics Difficulty 7.3 National olympiad, round 2 Prove it Belarus

Alice has n2n^2 sweets. These sweets are distributed among nn boxes (n>2n > 2). 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 nn 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: n=2mn = 2^m, where mNm \in \mathbb{N}, m>1m > 1.

The goal of Alice is to obtain exactly nn sweets in any box. The number ana-n is said to be the distance if aa 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 d1d_1 and d2d_2 of the same parity, then Alice can decrease the absolute values of the distances for these boxes if and only if d1d2d_1 \neq d_2. The necessity of this inequality is obvious. To prove the sufficiency we suppose that d1d2|d_1| \ge |d_2|:

1) if d1>d2|d_1| > |d_2|, then new distances of these boxes satisfy the inequality (d1+d2)/2(d1+d2)/2<(d1+d1)/2=d1|(d_1 + d_2)/2| \le (|d_1| + |d_2|)/2 < (|d_1| + |d_1|)/2 = |d_1|;

2) if d1=d2d_1 = -d_2, 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 kk distances are even and equal to some α>0\alpha > 0, and all other distances are odd and equal to some β<0\beta < 0.

Let n=2mn = 2^m (m>1m > 1). The sum of all distances is equal to zero at any moment. So, if kk distances are even and equal to α\alpha, and all other nkn-k distances are odd and equal to β\beta, then αk+β(nk)=0\alpha k + \beta(n-k) = 0 which yields k(αβ)=2mβk(\alpha - \beta) = 2^m\beta. But the last equality is impossible since αβ\alpha - \beta is odd and k<2mk < 2^m. Therefore, if n=2mn = 2^m (m>1m > 1), then Alice can equalize the numbers of the sweets in all boxes.

Now let n2mn \neq 2^m. Then n=(2p+1)2mn = (2p + 1) \cdot 2^m for some positive integer pp and nonnegative integer mm. Suppose that there are k=2mk = 2^m boxes with the distance α=2p\alpha = 2p and all other nk=2p2mn-k = 2p2^m boxes with the distance β=1\beta = -1. Note that this distribution of the sweets is possible since the equality αk+β(nk)=0\alpha k + \beta(n-k) = 0 holds. Since the numbers α\alpha and β\beta have the different parities, Alice cannot equalize the numbers of the sweets in all boxes.

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.