Let $n> 2$ be a positive integer. Given is a horizontal row of $n$ cells where each cell is painted blue or red. We say that a block is a sequence of consecutive boxes of the same color. Arepito the crab is initially standing at the leftmost cell. On each turn, he counts the number $m$ of cells belonging to the largest block containing the square he is on, and does one of the following: If the square he is on is blue and there are at least $m$ squares to the right of him, Arepito moves $m$ squares to the right; If the square he is in is red and there are at least $m$ squares to the left of him, Arepito moves $m$ cells to the left; In any other case, he stays on the same square and does not move any further. 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 will reach the rightmost cell.
Problem
Source: Iberoamerican 2022, Day 2, P1
Tags: combinatorics
02.10.2022 15:42
Consider a blue block of $b$ blue cells. Notice that if we step on it we advance $b$ cells and, in addition, in the best of cases we are in the last cell, so we will not be able to advance beyond $b-1+b = 2b-1$ cells forward. Let $b_1, b_2, \cdots b_l$ be the blue blocks, we consider the first case in which we need at least $2$ blocks. Notice that if we add the maximum ranges of each of them, we must have a distance of at least $n-1$: $$\sum_{i=1}^{l} (2|b_i|-1) \geq n-1 \Rightarrow 2k - 2 \geq 2k - l \geq n-1 \Rightarrow k \geq \left \lceil \frac {n+1}{2}\right \rceil$$ We name the cells $0, 1, \cdots, n-1$. If we had exactly $1$ block with $k < n$ blue cells, it should be at the beginning. Then, if we reach the block $n-1$, it happens that: $$k - (n-k) + k - (n-k) + \cdots + k = n-1 \to j(2k -n) + k = n-1$$So we have $2k-n \geq 1$ (otherwise $k=n-1$) then $k \geq \left \lceil \frac{n+1}{2}\right \rceil$ which is the same as we saw. For the example, where $n=2r$, we put $r$ blue cells, $1$ red, $1$ blue and $r-2$ red. So the path is $0 \to r \to r-1 \to 2r-1$ and we get there using $r+1$ blue cells. For the example, where $n=2r+1$, we put $r$ blue cells, $r-1$ red, $1$ blue, $1$ red. Then the path is $0 \to r \to 1 \to r+1 \to 2 \to \cdots \to r-2 \to 2r-2 \to r-1 \to 2r-1 \to 2r$ and we arrive using $r+1$ blue cells.
02.10.2022 21:32
This problem was proposed by me, Santiago Rodriguez from Colombia. I hope that you enjoy my problem. Here is my solution:
And as a little fun fact: Arepo or Arepito is the Colombian math olympiad mascot, named after a Colombian typical food, the arepa. He is this guy:
Attachments:
05.10.2022 08:51
Oooooo nice problem, Arepito Solved it all the way from Bogota during the Ibero First, notation: 1. Let a Mega-Block (MB) be the biggest block containing a square 2. Let $m_{i}$ be the $i$th MB from left to right 3. Let $c_{i}$ be the $i$th square from right to left 4. $m_{i},c_{j} \in{B}$ if they are blue and $m_{i},c_{j} \in{R}$ if they are red 5. Let $B>m_{i},c_{j}$ be the blue squares after $m_{i},c_{j}$ and $R>m_{i},c_{j}$ be the red squares after $m_{i},c_{j}$ WLOG assume that Arepito stops after getting to the $n$th square Consider $m_{h}\in{B} \rightarrow c_{n} \in m_{n'} \implies |m_{h}| \geq |m_{h+1}| + |m_{h+2}| + ... + |m_{n'}| \implies |B\geq m_{h}| \geq |R>m_{h}|$ Consider the $m_{r<h}\in R$ In order to jump $m_{r}\in R \exists m_{b<r}\in B: m_{b} \rightarrow m_{i>r} \implies |m_{b}|>|m_{r}|$ Let the set $B'=${$m_{b_1}, m_{b_2},..., m_{b_{b'}}$}$: m_{b_i} \rightarrow m_{j >b_i+1} \rightarrow ... \cancel{\rightarrow} m_{j\leq b_i+1} \implies |m_{b_i}|>|m_{b_i+1}|+|m_{b_i+2}|+...+|m_{j-1}|$ Note that it is possible to create $f:R \rightarrow B'$ such that each $m_r\in{R}$ is assigned with the last $m_{b_i}$ that jumps it Note that $f$ is surjective since each MB in $B'$ is the last MB to jump at least one $m_r$ $\therefore$ If $B'\neq \emptyset \implies |m_{b_1}|+|m_{b_2}|+...+|m_{b_{b'}}|>|R|-|R>m_h|\geq |R|-|m_h| \implies |B|\geq |m_h|+|m_{b_1}|+|m_{b_2}|+...+|m_{b_{b'}}|>|R| \implies |B|>|R|$ If $B'=\emptyset$ note that $m_1$ must jump $m_2 \implies m_1 \rightarrow C_n \implies |m_1|\geq n-|m_1|\implies |B|\geq |m_1|\geq \frac{n}{2} \implies |B|\geq \frac{n}{2}$ $\therefore k\geq \frac{n}{2}$ For the sake of contradiction assume that $k=\frac{n}{2}$ $ \implies 2|n, B'=\emptyset \implies |m_1|\geq n-|m_1| \implies \frac{n}{2}=|B|\geq |m_1|\geq \frac{n}{2} \implies |B|=|m_1|=\frac{n}{2}\implies |m_2|=|R|=\frac{n}{2}$ $\implies C_1\rightarrow C_{\frac{n}{2}+1} \rightarrow C_1 \rightarrow ... \rightarrow C_1 \rightarrow ... \implies \frac{n}{2}+1=n \implies n=2 \rightarrow \leftarrow$ $\therefore k>\frac{n}{2} \implies k\geq \lceil{\frac{n+1}{2}}\rceil$ Claim: $k=\lceil{\frac{n+1}{2}}\rceil$ Proof: For $n=2x+1$ take $AAA...ARRR...R, |m_1|=x+1, |m_2|=x \implies C_1\rightarrow C_{x+2}\rightarrow C_2 \rightarrow C_{x+3} \rightarrow C_3 \rightarrow ...\rightarrow C_x \rightarrow C_{2x+1=n} \checkmark$ For $n=2x$ take $AAA...ARARRR...R, |m_1|=x, |m_4|=x-2 \implies C_1\rightarrow C_{x+1}\rightarrow C_{x}\rightarrow C_{2x=n} \checkmark$ $\therefore k=\lceil{\frac{n+1}{2}}\rceil$ Q.E.D. Greeting from Perez and Ajolote, the Costa Rican and Mexican mascots
Attachments:
