Problem 10.8. Two bandits stole 300 gold coins. They decided to divide them as follows: the first bandit puts some coins (possibly all) into a bag, and the second bandit chooses who gets this bag; then this action is repeated several times. The division ends when

- either all the money is gone,
- or someone gets 11 bags - in this case, all the remaining money immediately goes to the other bandit.

What is the maximum number of coins that the first bandit can guarantee to get?
Answer: 146.

Solution. First, we will show that the first bandit can get at least 146 coins. His strategy will be to put 14 coins in each bag. First, note that he will always be able to do this: since $21 \cdot 14=294$, he will do this at least 21 times, and when the coins start to run out, the process will certainly be over (one of the bandits will get 11 bags).

Let's analyze how the game can end. If the first bandit has accumulated 11 bags, that's already 154 coins. In the other case, the second bandit, on the contrary, has no more than 11 bags, that is, no more than 154 coins. Therefore, the remaining coins are with the first bandit, which is at least 146.

Now we will show how the second bandit can guarantee himself 154 coins. His strategy is as follows: take bags with 14 coins or more for himself, and give bags with 13 coins or less to the first bandit.

Similarly, let's analyze how the game can end. If the second bandit finishes with 11 bags, he will have at least 154 coins. In the other case, the first bandit will finish with no more than 11 bags, which is no more than $11 \cdot 13=143$ coins. Then the second bandit will have at least 157 coins.

Remark. Let's indicate how to get the answer in the general case. Suppose there are $N$ coins in total, and each bandit can get no more than $k$ bags ($N \geqslant 2 k$). We will divide the coins into $2 k$ almost equal groups, so that either all groups have the same number of coins (if $N \vdots 2 k$), or the number of coins in the groups differs by no more than 1 (such a division is unique). We will order the groups in ascending order. By reasoning similar to the one provided above, we can show that the first bandit can guarantee himself the sum of the $k$ smaller groups of the division, and the second bandit can guarantee the sum of the $k$ larger groups.

## 11th Grade