Two sages are playing the following game. The numbers $0,1,2, \ldots, 1024$ are written down. The first sage crosses out 512 numbers (of his choice), the second crosses out 256 of the remaining, then the first crosses out 128 numbers, and so on. On the tenth step, the second sage crosses out one number; two numbers remain. After this, the second sage pays the first the difference between these numbers. How should the first sage play to his advantage? How should the second sage play? How much will the second sage pay the first if both play optimally? (Compare with problem $\underline{78710}$ and problem $\underline{78716}$.)
Answer: with correct play, the difference between the remaining numbers is 32 (as they say, the "cost of the game" is 32). The following considerations lead to this answer: the first player aims to maximize the difference between the remaining numbers and should always try to "thin out" the remaining set of numbers as much as possible, while it is advantageous for the second player to cross out numbers "from the edges." Of course, these considerations do not constitute a rigorous proof. To fully justify the answer, in this problem (as in the analysis of any game situation), two statements need to be proven: 1) no matter how the second player plays, the first can achieve no less than 32; 2) no matter how the first player plays, the second can lose no more than 32. To prove statement 1), we will indicate a strategy for the first player that guarantees, regardless of the second player's moves, that the difference between the two remaining numbers will be no less than 32. This strategy is described very simply: at each move, cross out every other number, i.e., the second, fourth, sixth, ... number from the remaining ones (we assume that the numbers are arranged in ascending order). Then after the 1st move, the difference between any adjacent remaining numbers will be no less than 2, after the 2nd move - no less than 4, after the 3rd move - no less than 8, after the 4th move - no less than 16, and after the 5th move - no less than 32. To prove statement 2), it is sufficient to indicate a strategy for the second player that will allow him, regardless of the first player's moves, to lose no more than 32. It consists of the following. On the first move, he crosses out all numbers less than 512 or all numbers greater than 512 (it is clear that either of these sets will not exceed 256). After this, the difference between the extreme remaining numbers will be no more than 512. Similarly, on the second move, he can ensure that all remaining numbers are in one of the segments [0, 256]; [256, 512]; [512, 768]; [768, 1024], that is, reduce the difference between the extreme numbers to at least 256. In the same way, on the 3rd move, he can reduce this difference to 128, on the 4th move - to 64, and on the 5th move - to 32. Of course, similarly, it could be proven that if the game consists of $n$ moves and starts with the numbers $0,1,2, \ldots, 2^{2 n}$, then the "cost of the game" is $2^{\text {n }}$. However, a detailed study of a similar game starting with an arbitrary set of numbers (not necessarily an arithmetic progression) represents a significantly more difficult task.

## Answer

With correct play, the difference between the remaining numbers is 32 (as they say, the "cost of the game" is 32).