Problem 11.3. There are 100 pies arranged in a circle, 53 of which are with cabbage, and the rest are with rice. Alexei knows which ones are with what, and he wants to choose 67 consecutive pies such that among them there are exactly $k$ with cabbage. For which $k$ is he guaranteed to be able to do this regardless of the arrangement of the pies? Provide all possible options and prove that there are no others.
Answer: 35 or 36.

Solution. A set of 67 consecutive pies will be called a segment. Two segments will be called adjacent if the sets of pies in them differ by only a pair of extreme ones, that is, the segments differ by a shift of one pie. Then, in two adjacent segments, the number of pies with cabbage obviously differs by no more than 1. Consequently, if in some two segments there are $a$ and $b$ pies with cabbage, then for any integer $c$ between $a$ and $b$, there is a segment containing exactly $c$ pies.

Let's move on to solving the problem. We will prove that there is a segment containing at least 36 pies with cabbage and a segment containing no more than 35. For this, we will number the pies from 1 to 100 so that the 1st pie is with rice. Consider segments of pies from the 1st to the 67th, from the 68th to the 34th (through the 100th), and from the 35th to the 1st (through the 100th). In total, these three segments contain all pies except the first one twice, and the first one three times. Thus, they contain $2 \cdot 53=106$ pies with cabbage in total, which means that in some of the three segments, there are at least 36 pies with cabbage, and in some no more than 35.

Considering the above, we conclude that there must be a segment with exactly 35 pies and a segment with exactly 36 pies.

We will prove that no other quantities may exist. For this, we will first place 50 pies with rice and 50 with cabbage alternately so that all pies with odd numbers are with rice. In such an arrangement, each segment starting with a pie with rice contains 33 pies with cabbage, and starting with a pie with cabbage contains 34 pies with cabbage. It remains to correctly replace three pies with rice with pies with cabbage so that all segments contain 35 or 36 pies with cabbage. For this, it is sufficient to replace the pies with numbers 1, 33, and 67. Then, in all segments except the segment from the 1st to the 67th, the number of pies with cabbage will increase by exactly 2, and in the segment from the 1st to the 67th, it will increase by 3, which will give the required result.

## Criteria

## The following criteria are cumulative:

3 6. "Example". It is shown that no $k$ other than 35 and 36 are suitable.

4 b. "Estimate". It is proven that $k=35$ and $k=36$ are suitable. In the absence of a complete proof of the "estimate," the following partial advancements are cumulative:

2 6. It is proven that if there are segments with $a$ and $b$ pies, then there are all intermediate ones.

1 6. It is proven that there is a segment with no fewer than 35 pies.

1 6. It is proven that there is a segment with no more than 36 pies.

## Kurchatov School Olympiad in Mathematics - 2019 Final Stage.