2022 OIM Problems/Problem 4

Problem

Let $n > 2$ be a positive integer. There is a horizontal row of $n$ cells such that each cell is colored red or blue. A block is a contiguous sequence of similarly colored cells. Arepito the crab is initially on the leftmost cell of the row. In each turn, he counts the number $m$ of cells of the longest block containing the cell he is currently on and performs one of the following actions:

  • If he is on a blue cell and there are at least $m$ cells to his right, Arepito moves $m$ cells to the right;
  • If he is on a red cell and there are at least $m$ cells to his left, Arepito moves $m$ cells to the left;
  • Otherwise he stays on the cell he is currently on and does not move anymore.

For each $n$, determine the smallest integer $k$ for which there is an initial coloring of the row with $k$ blue cells for which Arepito can reach the rightmost cell of the row.

Solution

This problem needs a solution. If you have a solution for it, please help us out by adding it.

See also

https://sites.google.com/uan.edu.co/oim-2022/inicio