Problem 8.6. (20 points) On the table, there are 55 piles of candies. In one pile, there is 1 candy, in another - two, in the third - 3, ..., in the last - 55. Petya and Vasya are playing the following game, taking turns; Petya starts. In one move, a player takes one candy from any pile. If a player takes the last candy from a pile, they eat it, otherwise they throw it away. The game continues until all candies from the piles are either eaten or thrown away. What is the maximum number of candies that Petya can guarantee to eat?
Answer: 1.

Solution. It is clear that Petya can eat 1 candy, for example, if he takes a candy from the pile with 1 candy on his very first move.

We will prove that Vasya can prevent Petya from eating more than 1 candy. For this, Vasya will act as follows. If there is exactly 1 candy left in any pile, he will take it and eat it. If there are no piles with 1 candy, he will take a candy from any pile with more than 2 candies.

First, let's understand why Vasya will always be able to make a move according to this strategy. Suppose that at some point Vasya cannot make a move, that is, there are no more than 2 candies in each pile, and there are no piles with 1 candy. Then, there are exactly 2 candies in each pile, and before Vasya's move, there is an even number of candies left. On the other hand, initially, there were $1+2+\ldots+55=\frac{55 \cdot 56}{2}=1540$ candies on the table, which is an even number. Therefore, after Petya's move, there should be an odd number of candies left, and after Vasya's move, there should be an even number, which is a contradiction.

Now, let's prove that with this strategy, Petya will not be able to eat more than 1 candy. Note that if after some move by Petya there are no piles with 1 candy, then there will never be any such piles again. Indeed, the piles from which Vasya takes candies will not consist of only 1 candy after his move, and all piles with 1 candy that Petya leaves will be immediately eaten by Vasya on the next move.

Thus, if Petya eats the pile with 1 candy on his first move, he will never eat any more. If he does not do this, Vasya will eat it on the next move, and Petya will be able to create no more than one new pile with 1 candy during his first move. If such a pile does appear (from a pile with 2 candies), and Petya does not eat it on his second move, he will not eat anything at all, as he will not be able to create a new pile with 1 candy on his second move. If he does eat it, then, as before, he will not be able to eat anything more.

Therefore, Vasya has a strategy that allows him to prevent Petya from eating more than 1 candy.

## Criteria

The highest applicable criterion is used:

20 points. The correct strategy for Vasya is provided with an explanation.

18 points. The problem is correctly solved under the unproven assumption that Petya will eat 1 candy from the pile with 1 candy on his first move.

10 points. The correct strategy for Vasya is provided without a correct explanation.

5 points. The problem is solved under the assumption that neither player touches piles with 2 candies if there is at least one pile of a different size.

0 points. Only the answer is provided.