Shen A.H.

There is an infinite one-way strip of cells, numbered with natural numbers, and a bag with ten stones. Initially, there are no stones in the cells of the strip. The following actions can be performed:

- move a stone from the bag to the first cell of the strip or vice versa;
- if there is a stone in the cell with number $\$ \mathrm{i} \$$, then a stone can be moved from the bag to the cell with number $\$ \mathrm{i}+1 \$$ or vice versa.

Is it possible, acting according to these rules, to place a stone in the cell with number 1000?
Note that for each action, there is an inverse action. Therefore, if we move from situation $A$ to situation $B$ by following the rules, we can move from situation $B$ back to situation $A$ by following the rules.

We will show by induction that if there is a reserve of $n$ stones, then, acting according to the above rules, we can place a stone in any cell from $1$ to $2^n - 1$.

Base case: $n=1$. This is obvious.

Inductive step. Suppose we have proven that with a reserve of $n$ stones, we can place a stone in all cells up to $(2^n - 1)$. Now suppose we have $n$ black stones and one red stone. We will proceed as follows:

1) Without removing the red stone from the bag, we will ensure that a black stone ends up in the $(2^n - 1)$-th cell. This can be done by the inductive hypothesis.
2) Place the red stone in the $2^n$-th cell.
3) Perform the operations as in step (1), but in the opposite and reverse order. It is clear that the red stone will not hinder this. In the end, all black stones will be back in the bag, and on the strip, there will be exactly one stone - the red stone in cell $2^n$. We agree that we will not remove the red stone further.
4) The cells with numbers from $2^n + 1$ to $2^{n+1} - 1$ form a strip of length $2^n - 1$. The inductive hypothesis applies to $n$ stones for this strip, as the red stone allows operations with the leftmost cell of this strip. Therefore, we can place a stone in the last cell.

Thus, with a reserve of 10 stones, we can place a stone in all cells from $1$ to $1023 = 2^{10} - 1$.

## Answer

Yes.

|  | [ Examples and counterexamples. Constructions $]$ | Difficulty: 4 |
| ---: | :--- | ---: |
| Problem $\underline{66704}$ Topics: |  |  |
| $\left[\begin{array}{ll}\text { Numerical inequalities. Comparing numbers. }\end{array}\right]$ | Classes: $8,9,10,11$ |  |

![](https://cdn.mathpix.com/cropped/2024_05_06_0918ecac094e52bfe73bg-01.jpg?height=49&width=226&top_left_y=2285&top_left_x=1)

On the street, houses stand opposite each other, a total of 50 pairs. On the right side of the street, houses have even natural numbers, and on the left side, they have odd natural numbers. The numbers increase from the beginning of the street to the end on each side, but they do not necessarily go consecutively (gaps are possible). For each house on the right side of the street, the difference between its number and the number of the house opposite was found, and it turned out that all the found numbers are different. The largest house number on the street is $n$. Find the smallest possible value of $n$.

## Solution

Example. Suppose the numbers on each side of the street form an arithmetic progression: on the right side $-2, 4, \ldots, 100$, and on the left side $-1, 5, \ldots, 197$. Then the differences form an arithmetic progression with a step of $2$, so they will be different.

Estimate. Note that all these differences are odd.

First method. Approach the first house on one side of the street. Walk along the street, then cross to the opposite side at some point and walk to the end. While walking along the street, the number of each subsequent house was at least 2 more than the previous one. Therefore, the difference in house numbers at the beginning and end of the street is at least $2 \cdot 49$ plus the differences in the numbers of the two pairs of houses where we crossed the street. We will show that we can choose the starting side of the street and two pairs of houses such that these two differences sum to at least 98. Then we will get that the number of the last house is at least $1 + 98 + 98 = 197$.

Indeed, all the differences are different, so there are two that differ by at least 98. We need to cross the street at the pairs of houses with these differences. If the smaller of the two differences is closer to the beginning of the street than the larger one, we should start the walk from the even side. Then the smaller difference will enter the sum with a minus, and the larger one with a plus. If the smaller difference is further from the beginning, we should start from the odd side.

Second method. Suppose $b_1 > \ldots$, then $a_i = b_i - d \geq b_j + 2(i - j) - d$, and $a_i - a_j \geq D - d + 2(j - i) \geq 2(j - i) + 2 \cdot 49$. Therefore, $a_{50} - a_1 \geq 2 \cdot 49 + 2 \cdot 49 = 196$, from which $a_{50} \geq 197$. If $i < j$ and $b_i < b_j$, then $a_i = b_i - d \geq b_j + 2(i - j) - d$, and $a_i - a_j \geq D - d + 2(j - i) \geq 2(j - i) + 2 \cdot 49$. Therefore, $a_{50} - a_1 \geq 2 \cdot 49 + 2 \cdot 49 = 196$, from which $a_{50} \geq 197$.

![](https://cdn.mathpix.com/cropped/2024_05_06_0918ecac094e52bfe73bg-02.jpg?height=48&width=798&top_left_y=702&top_left_x=1)

## Answer

197. 

## Problem