Bakayev E.V.

A hundred bear cubs found berries in the forest: the youngest managed to grab 1 berry, the next older cub - 2 berries, the next one - 4 berries, and so on, with the oldest getting \(2^{99}\) berries. The fox suggested they divide the berries "fairly." She can approach two bear cubs and distribute their berries equally between them, and if there is an extra berry, the fox eats it. She continues these actions until all the bear cubs have the same number of berries. What is the smallest number of berries the fox can leave the bear cubs?
Notice that at each step, if both participating cubs had at least one berry, then each of them will have at least one berry left. Therefore, in the end, each cub will have at least one berry.

We will prove that the fox can leave each cub exactly one berry, that is, transition from the position (1, $2, \ldots, 2^{99}$) to the position (1, 1, ..., 1). To do this, we will prove by induction that in the case of $n$ cubs, the fox can transition from the position (1, $2, \ldots, 2^{n-1}$) to the position (1, 1, ..., 1, $2^{n-1}$), and from the latter to the position (1, 1, ..., 1).

Base case. For $n=1$, all three positions coincide.

Inductive step. From the position (1, 2, ..., $2^{n-1}$, $2^n$), ignoring the last cub, we can, by the inductive hypothesis, first transition to

(1, 1, ..., 1, $2^{n-1}$, $2^n$), and then to (1, 1, ..., 1, $2^n$). Engaging the last two cubs, the fox transitions to

the position (1, 1, ..., 1, $2^{n-1}$, $2^{n-1}$). Now, ignoring the last cub again, we can transition to the position (1, 1, ..., 1, $2^{n-1}$), and from there, ignoring the first cub, to the position (1, 1, ..., 1).

## Answer

100 berries.