Kanel-Belov A.Y.

Ali-Baba and the bandit are dividing a treasure consisting of 100 gold coins arranged in 10 piles of 10 coins each. Ali-Baba chooses 4 piles, places a cup next to each, and sets aside several coins from each pile (not less than one, but not the entire pile). The bandit must then rearrange the cups, changing their initial positions, after which the coins are poured from the cups into the piles next to which the cups are placed. Then Ali-Baba again chooses 4 piles out of 10, places cups next to them, and so on. At any point, Ali-Baba can leave, taking with him any three piles of his choice. The remaining coins go to the bandit. What is the maximum number of coins Ali-Baba can take if the bandit also tries to get as many coins as possible?
Let's show that Ali-Baba can achieve that in 7 piles there are no more than 4 coins, while the robber can achieve that there are no piles containing fewer than 4 coins. Therefore, Ali-Baba will take $100 - 7 \cdot 4 = 72$ coins.

First, let's prove that the robber can act in such a way that there are no piles containing fewer than 4 coins. Indeed, this is true for the initial situation. Suppose that at some step this is true and part of the coins have already been placed in cups. Then, if two cups contain the same number of coins, the robber can swap these cups and the situation does not change. If the number of coins in all cups is different, then in the two largest of them there are at least 3 and 4 coins, respectively, and the robber can swap these cups. As a result, in all new piles there will again be no fewer than 4 coins.

Now let's show that Ali-Baba can achieve that in 7 piles there are no more than 4 coins. Suppose there are 4 piles, each containing more than 4 coins, and $x_{1}^{(0)} \geq x_{2}^{(0)} \geq x_{3}^{(0)} \geq x_{4}^{(0)} \geq 5$ are the quantities of coins in these piles. We will show that Ali-Baba can achieve that in one of these piles there will be fewer than 4 coins, while the number of coins in each of the remaining six piles does not change. Let's distribute these piles as follows:

$$
x_{1}^{(0)}=y_{1}+1, \quad x_{2}^{(0)}=y_{2}+2, \quad x_{3}^{(0)}=y_{3}+3, \quad x_{4}^{(0)}=y_{4}+4
$$

by placing 1, 2, 3, and 4 coins in the cups, respectively. After swapping the cups, we get new piles consisting of

$$
x_{1}^{(1)}=y_{1}+z_{1}, \quad x_{2}^{(1)}=y_{2}+z_{2}, \quad x_{3}^{(1)}=y_{3}+z_{3}, \quad x_{4}^{(1)}=y_{4}+z_{4}
$$

coins, where $z_{1}, z_{2}, z_{3}$, and $z_{4}$ are some permutation of the numbers 1, 2, 3, and 4. The process is then repeated by replacing the numbers $x_{1}^{(0)}, \ldots, x_{4}^{(0)}$ with the numbers $x_{1}^{(1)}, \ldots, x_{4}^{(1)}$ arranged in non-increasing order.

We will prove that at some step the process will terminate, i.e., in one of these piles there will be fewer than 5 coins. One of the following three possibilities will occur:

1) $x_{1}^{(1)}>x_{1}^{(0)}$ (if the first cup is swapped);
2) $x_{1}^{(1)}=x_{1}^{(0)}, x_{2}^{(1)}>x_{2}^{(0)}$ (if the first cup is left in place and the second cup is swapped);
3) $x_{1}^{(1)}=x_{1}^{(0)}, x_{2}^{(1)}=x_{2}^{(0)}, x_{3}^{(1)}>x_{3}^{(0)}$ (if the first two cups remain in place).

On each step, the number of coins in the first pile does not decrease. Therefore, the number of steps where the first possibility is realized is finite. The total number of coins in the first and second piles also does not decrease, so the number of steps where the second possibility is realized is also finite. Similarly, it can be verified that the number of steps realizing the third possibility is also finite. Therefore, at some step the process will terminate, which corresponds to the fact that in some pile there will be no more than 4 coins. In this case, the number of piles with no more than 4 coins will increase. By repeating this process, eventually we will reach a point where there are no more than three piles containing more than 4 coins.

Send a comment