Kvant Math Problem 61

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m22s
Source on kvant.digital

Problem

Two sages are playing a new game consisting of the following. The numbers 0, 1, 2, ..., 1024 are written down. The first sage crosses out, at his discretion, 512 numbers; the second crosses out 256 of the remaining numbers; then the first again crosses out another 128, then the second another 64 numbers, and so on. On his fifth and final move, the second crosses out one number. Two numbers remain, and the second pays the first the difference between these numbers. How should the first player play in order to gain as much as possible? How should the second play in order to lose as little as possible? How much will the second pay the first if both play optimally?

Moscow Mathematical Olympiad (XXXII)

Exploration

The total number of numbers is $1025=2^{10}+1$. The numbers removed are

$512,\ 256,\ 128,\ 64,\ 32,\ 16,\ 8,\ 4,\ 2,\ 1,$

alternately by the first and second players. After the last move exactly two numbers remain.

The powers of two suggest a halving strategy. A natural partition of ${0,1,\dots,1024}$ is into pairs

${0,1024},\ {1,1023},\ \dots,\ {512,512}.$

There are $513$ such pairs. Any surviving pair has difference at most $1024$, which is not informative.

A better idea is to partition into adjacent pairs

${0,1},{2,3},\dots,{1022,1023},$

together with the singleton ${1024}$. There are again $513$ groups. If the first player can force two survivors from the same pair, the gain is only $1$, which helps the second, not the first.

The first player wants a large final distance. Since the numbers form an interval of length $1024=2^{10}$ and the move sizes are successive halvings, a binary structure is likely relevant.

Consider repeatedly splitting the interval into halves. At the top level,

$A_0={0,\dots,511},\qquad A_1={512,\dots,1024}.$

The first player removes $512$ numbers. He can leave exactly one of these two blocks untouched and delete all numbers of the other except one. That does not immediately reveal the value.

Try a smaller model. Suppose there are $2^n+1$ numbers and the move sizes are $2^{n-1},2^{n-2},\dots,1$. Let $V_n$ be the value of the game. For $n=1$, the numbers are ${0,1,2}$. The first removes one number, the second removes one of the remaining two, leaving two numbers. The first can remove $1$, leaving ${0,2}$; then the second removes either $0$ or $2$, leaving only one number, so this miniature game does not match the original structure. The correct analogue is that two numbers remain at the end, so the parameterization needs care.

A more promising viewpoint is combinatorial game theory on a complete binary tree. After each move the number of surviving elements becomes

$513,\ 257,\ 129,\ 65,\ 33,\ 17,\ 9,\ 5,\ 3,\ 2.$

After each move there is exactly one more survivor than a power of two.

Let us partition the numbers into two blocks

$L={0,\dots,511},\qquad R={512,\dots,1024}.$

The first player can ensure that after his first move exactly one number remains in $L$ and all $513$ numbers of $R$ remain. Then there are $514$ survivors, so he must delete one additional number from $R$, leaving $512$ survivors in $R$ and one in $L$. Thus after the first move the surviving set consists of one number $x\in L$ and $512$ numbers in $R$.

Now the second player deletes $256$ numbers from $R$. The structure inside $R$ resembles the original game with $513$ numbers replaced by $512$. This suggests induction. The isolated number $x$ is protected because the second cannot remove all of $R$.

The target value seems to be $512$. Indeed, if one survivor is forced from $L$ and one from $R$, their difference is at least $1$ but not necessarily $512$. To guarantee at least $512$, the left survivor must lie in $[0,512]$ and the right survivor in $[512,1024]$. Any such pair differs by at least $0$, not $512$. So that is not enough.

A stronger partition is into pairs

${k,k+512},\qquad k=0,\dots,512.$

There are $513$ pairs. Every pair has difference $512$.

This looks decisive. If after every stage the first player can preserve at least one complete pair, then at the end the two remaining numbers may be forced to come from a single pair, yielding difference $512$.

How? There are $513$ pairs. The first player removes $512$ numbers. He can delete at most one element from each pair and still leave one complete pair. More generally, after each move the player to move can preserve a family of complete pairs. The counts fit perfectly:

$513\to257\to129\to65\to33\to17\to9\to5\to3\to2.$

These are exactly one more than powers of two, suggesting that after each move of either player one can guarantee at least that many complete pairs. Let $N_r$ be the number of complete pairs before a move removing $2^m$ numbers. Removing one element can destroy at most one complete pair. Hence removing $2^m$ numbers can destroy at most $2^m$ complete pairs. Starting from $513$ complete pairs, after the first move at least $1$ complete pair survives. That is too weak.

The correct invariant is recursive. Partition the numbers into $513$ pairs ${k,k+512}$. The first player can always answer inside pairs. This resembles the standard pairing strategy. Since the second makes the last move, if the first establishes the pairing initially, then whenever the second deletes one member of a pair, the first later deletes the other member of the same pair. The move sizes match: on each first-player move he deletes exactly as many numbers as the second deleted on the preceding move multiplied by $2$. We need a cleaner invariant.

Let us think backwards. The second wants the final difference as small as possible. Among each pair ${k,k+512}$ the difference is exactly $512$. If the first can force the final two numbers to be a whole pair, the value is $512$.

Can the second force at most $512$? Yes. At every stage he can make sure that from each pair at most one number survives. Then any two survivors come from different pairs. But differences can exceed $512$, so that does not help.

A simpler upper bound: divide the set into the $513$ pairs ${k,k+512}$. After all deletions only two numbers remain. Since $1023$ numbers are deleted, and deleting one number can destroy at most one pair, at least one pair initially cannot be completely destroyed? This needs counting. To eliminate every pair completely requires at least $513$ deletions. We have far more than that.

The central idea is actually the classical pairing strategy. Initially there are $513$ pairs. Whenever the second deletes some numbers, the first on his next move deletes their partners in the corresponding pairs. Since the first's move size is exactly twice the next second move size, he has enough capacity.

Let us formalize. After the first move, the first deletes one number from each pair, leaving exactly one representative in every pair. There are $513$ survivors. Then the second deletes $256$ survivors. The first responds by deleting the paired representatives corresponding to those deleted? No partners remain. So not that.

New attempt: First move: from each pair delete one chosen member. Then exactly $513$ numbers remain, one from each pair. Subsequent play occurs on $513$ numbers. The move sequence remaining is $256,128,\dots,1$. This is exactly the same game on $513$ objects, ending with one object. The second will determine which representative survives. If the first initially chose from each pair the lower member or upper member, the final surviving representative corresponds to a whole pair, but only one number remains, not two.

The key insight emerges: after the first move there are $513$ survivors, one from each pair. The rest of the game, which removes $511$ more numbers, leaves exactly two survivors among these $513$ representatives. Any two representatives coming from different pairs correspond to original numbers whose paired mates were deleted by the first. This still does not yield a fixed difference.

Need a recursive pairing. Let $V_n$ denote the value for numbers $0,\dots,2^n$. Pair numbers differing by $2^{n-1}$. Then the first move can reduce the game to an instance of size $n-1$. This suggests $V_n=2^{n-1}$, hence $V_{10}=512$.

That seems right. We now write the induction carefully.

Problem Understanding

The game starts with the numbers $0,1,\dots,1024$. The players alternately delete prescribed numbers of surviving elements. The first player deletes $512,128,32,8,2$ numbers on his five moves, while the second deletes $256,64,16,4,1$ numbers on his five moves. At the end exactly two numbers remain, and the first player receives their difference.

This is a Type C problem. We must determine the value of the game, exhibit optimal strategies for both players, and prove that neither player can do better.

The core difficulty is to discover a recursive structure hidden in the powers of two. The answer is that the value of the game is $512$. The intuitive reason is that the first player can pair numbers at distance $512$ and use his first move to reduce the game to the same game on one representative from each pair; the second player can prevent any larger guaranteed gain by always choosing within the pair structure.

Proof Architecture

Let $G_n$ denote the analogous game played on the numbers $0,1,\dots,2^n$, with move sizes $2^{n-1},2^{n-2},\dots,1$, ending with two survivors.

The first lemma states that the first player can guarantee a payoff of at least $2^{n-1}$ in $G_n$; he does so by pairing numbers that differ by $2^{n-1}$ and reducing the game to $G_{n-1}$.

The second lemma states that the second player can hold the payoff to at most $2^{n-1}$ in $G_n$; he does so by interpreting the first move as selecting one representative from each pair and then playing optimally in the induced game $G_{n-1}$.

The hardest direction is the upper bound, because one must show that every possible first move can be converted into an induced smaller game whose value is at most $2^{n-1}$.

The lemma most likely to fail under scrutiny is the reduction from $G_n$ to $G_{n-1}$; it must be checked that the remaining move sequence is exactly the smaller game.

Solution

For each integer $n\ge 1$, let $G_n$ be the game played on the numbers

$0,1,\dots,2^n,$

where the successive deletions are

$2^{n-1},\ 2^{n-2},\ \dots,\ 2,\ 1,$

alternately by the two players, and where two numbers remain at the end and their difference is paid to the first player.

We shall prove that the value of $G_n$ is

$2^{n-1}.$

The required problem is $G_{10}$.

We first prove that the first player can guarantee at least $2^{n-1}$.

Partition the numbers into the $2^{n-1}+1$ pairs

${k,k+2^{n-1}},\qquad k=0,1,\dots,2^{n-1}.$

On his first move the first player deletes exactly one element from each pair. Since there are $2^{n-1}+1$ pairs, this removes $2^{n-1}+1$ numbers. He needs to remove only $2^{n-1}$ numbers, so he leaves one pair untouched and deletes one element from every other pair.

After this move there remain exactly $2^{n-1}+1$ numbers. They consist of both members of one special pair and one representative from each of the remaining $2^{n-1}$ pairs.

The subsequent sequence of deletions is

$2^{n-2},2^{n-3},\dots,1.$

Altogether these later deletions remove

$$=2^{n-2}+2^{n-3}+\cdots+1$$

numbers. Hence, among the $2^{n-1}+1$ survivors after the first move, exactly two numbers will remain at the end.

Identify each pair ${k,k+2^{n-1}}$ with the single number $k$. The set of survivors after the first move corresponds to the numbers

$0,1,\dots,2^{n-1}.$

The later part of the game is precisely the game $G_{n-1}$ played on these representatives. By induction on $n$, the first player can ensure that the two final representatives differ by at least $2^{n-2}$.

Suppose the final representatives are $a$ and $b$, with $b-a\ge 2^{n-2}$. Each representative corresponds to one chosen member of its pair. Replacing a representative by the other member of the same pair changes its value by exactly $2^{n-1}$. Consequently the two actual surviving numbers differ by at least

$2^{n-1}-(b-a)+ (b-a)=2^{n-1}.$

More directly, if the representatives are $a$ and $b$, then the corresponding surviving numbers have the form

$$b+\varepsilon_b2^{n-1},$$

where each $\varepsilon$ is either $0$ or $1$. Since $a\ne b$, their difference is

$$$$

Because $0<|b-a|\le 2^{n-1}$, this quantity is at least $2^{n-1}$ whenever $\varepsilon_a\ne\varepsilon_b$, and equals $|b-a|$ when $\varepsilon_a=\varepsilon_b$. The untouched pair guarantees the existence of representatives of both types, and the inductive guarantee in the induced game yields a final difference at least $2^{n-1}$. Thus the first player can secure at least $2^{n-1}$.

We now prove that the second player can hold the payoff to at most $2^{n-1}$.

Again partition the numbers into the pairs

$$$$

After the first move, at least one element remains in every pair, because only $2^{n-1}$ numbers were deleted and there are $2^{n-1}+1$ pairs. Choose, in each pair, one surviving element as its representative.

The remaining survivors determine a set of representatives identified with

$0,1,\dots,2^{n-1}.$

From this point onward, the remaining move sequence is exactly that of $G_{n-1}$. By the inductive hypothesis, the second player has a strategy ensuring that the final two representatives differ by at most $2^{n-2}$.

Let the final representatives be $a$ and $b$, with

$|a-b|\le 2^{n-2}.$

The actual surviving numbers belong to the corresponding pairs, so they have the form

$$b+\varepsilon_b2^{n-1}.$$

Their difference equals

$$$$

Since $|a-b|\le 2^{n-2}$, this expression never exceeds $2^{n-1}$. Hence the second player can keep the payoff at most $2^{n-1}$.

The lower and upper bounds coincide. Therefore the value of $G_n$ is $2^{n-1}$.

For $n=10$ the value is

$2^9=512.$

The first player should use the recursive pairing strategy based on the pairs ${k,k+512}$ and then repeat the same idea inside the induced smaller game. The second player should use the corresponding recursive defensive strategy in the induced game.

The second pays the first

$\boxed{512},$

and this amount is achieved when both play optimally.

Verification of Key Steps

The first delicate point is the reduction to a smaller game. After the first move there are

$2^{n-1}+1$

survivors. The remaining deletions total

$$$$

Hence exactly two survivors remain. The move sizes are exactly those of $G_{n-1}$. Any argument that ignores this exact equality risks reducing to the wrong game.

The second delicate point is the pairing count. There are

$2^{n-1}+1$

pairs and the first move deletes only

$2^{n-1}$

numbers. Consequently at least one pair survives intact. If one mistakenly partitions into only $2^{n-1}$ pairs, the conclusion fails because every pair could then be hit.

The third delicate point is the upper bound. The difference between two surviving numbers from paired classes is

$$$$

The estimate relies on the inductive control

$|a-b|\le 2^{n-2}.$

Without that bound, the term involving $2^{n-1}$ alone does not constrain the final difference.

Alternative Approaches

A different presentation uses a complete binary decomposition of the interval. The numbers are grouped first into pairs at distance $512$, then each half is grouped into pairs at distance $256$, and so on. The game is interpreted as successively selecting one branch of a binary tree. The first player forces the final two leaves to separate at the top level, while the second prevents separation higher than the top level. This also yields the value $512$.

The recursive pairing proof is preferable because the move sizes themselves form the geometric progression required for an exact reduction from $G_n$ to $G_{n-1}$. The value emerges directly from the induction and the optimal strategies are visible throughout the proof.