Competition problem — Combinatorics

Library / /2 of 10

Combinatorics Difficulty 7.8 National olympiad, round 2 Prove it Netherlands

Jesse and Tjeerd are playing a game. Jesse has $n \ge 2$ stones. There are two boxes: in the black box there is space for half of the stones (rounded down) and in the white box there is space for half of the stones (rounded up). Jesse and Tjeerd alternate turns, with Jesse as first player. In his turn, Jesse takes one new stone, writes a positive real number on the stone and puts it in one of the boxes which is not full yet. Tjeerd can see all the numbers on the stones in each of the boxes and is allowed to move one stone of his choice to the other box, if that other box is not full yet, but he is also allowed to choose to do nothing. The game stops when both boxes are full. If the total value of the stones in the black box is greater than the total value of the stones in the white box, Jesse wins; otherwise Tjeerd wins. Determine for each $n \ge 2$ who can always win this game (and give a winning strategy).

Solution

We will show that the capacity of the two boxes does not matter, as long as the total capacity is $n$ (and at least 1 for each box). Jesse can always win this game, and can do that by first playing the power $2^0 = 1$ of two, and then in each following turn the next power of two that is smaller or greater. That means: if he played the numbers
$2^{-i}, 2^{-(i-1)}, \dots, 2^{-1}, 2^{0}, 2^{1}, \dots, 2^{j-1}, 2^{j}$
at a certain moment, he will play either $2^{-(i+1)}$ or $2^{j+1}$ in his next turn.
By playing cleverly, Jesse can make sure that the greatest power of two among the stones played so far is always contained in the black box. We will prove this by induction. In his first move, he puts the stone with value $2^0$ in the black box and the claim is true; this is the base case of the induction. When it is his turn again, and Tjeerd moved the greatest power of two so far, which according to the induction hypothesis was contained in the black box, to the white box, then the black box actually has a free space, and Jesse can put a new greater power of two in there, and the claim is true. If Tjeerd moved some other stone or did nothing, then the greatest power of two so far is still in the black box, and Jesse can play a smaller power of two; it does not matter where he puts it. Also in this case, the claim is true. This proves the induction step, and the claim is proved.

Therefore, after playing the last stone, the greatest power of two is in the black box. It is greater than the sum of all smaller powers of two played ( $2^j > 2^j - 2^{-i} = 2^{j-1} + 2^{j-2} + \dots + 2^{-(i-1)} + 2^{-i}$ ), hence it is certainly greater than the sum of the powers of two in the white box. Therefore, the total value inside the black box is greater than the total value in the white box. $\square$

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.