Let $m$ be a positive integer with $m \leq 2024$. Ana and Banana play a game alternately on a $1\times2024$ board, with squares initially painted white. Ana starts the game. Each move by Ana consists of choosing any $k \leq m$ white squares on the board and painting them all green. Each Banana play consists of choosing any sequence of consecutive green squares and painting them all white. What is the smallest value of $m$ for which Ana can guarantee that, after one of her moves, the entire board will be painted green?
Problem
Source: Brazilian Mathematical Olympiad 2023, Level 3, Problem 5 / Level 2, Problem 6
Tags: game, combinatorics, board
bruckner
22.10.2023 13:10
My problem.
The answer is $m = \left\lceil 2(\sqrt{n+1}-1) \right\rceil$.
(But since $n=2024=45^2-1$, we're just fine)
Banana's strategy to ensure that $m$ is at least this is to always choose a sequence of consecutive numbers of maximum size.
Consider the last move of Banana before Ana paints everything, which was to erase a consecutive block of ones of size $a$:
\[ [b_1] [b_2] \cdots \underbrace{111 \dots 111}_a \cdots [b_{t-1}] [b_t], \]where $[b_i]$ is a block with $z_i > 0$ zeros, and $0 \leq u_i \leq a$ ones.
Hence:
\[ m \geq a + \sum z_i \]and
\[ n = a + \sum z_i + \sum u_i \implies n \leq (t+1)a + \sum z_i \implies n \leq m+ta \implies m \geq n-ta \]On the other hand, we have $m \geq a + \sum z_i \geq a + t \geq 2 \sqrt{ta} \implies ta \leq \frac{m^2}{4}$.
Thus,
\[ m \geq n-ta \geq n-\frac{m^2}{4} \implies m^2+4m \geq 4n \implies (m+2)^2 \geq 4(n+1) \implies m \geq 2(\sqrt{n+1}-1) \]
Let's prove that this $m$ indeed works.
Let's do a little trick in reverse and show that for $n = \left\lfloor \frac{m^2}{4} \right\rfloor + m$, it works.
(If $n$ is less than the maximum value and we want to do it with the same $m$, just ignore the last few places and repeat the strategy.)
Note that $\left\lfloor\frac{m^2}{4}\right\rfloor+m = \left(\left\lceil\frac{m}{2}\right\rceil+1\right)\left(\left\lfloor\frac{m}{2}\right\rfloor+1\right)-1$,
and consider the division of the $n$ cells into blocks as follows:
\[ \underbrace{\qquad}_{\left\lfloor \frac{m}{2} \right\rfloor}*\underbrace{\qquad}_{\left\lfloor \frac{m}{2} \right\rfloor}*\cdots*
\underbrace{\qquad}_{\left\lfloor \frac{m}{2} \right\rfloor}, \]where there are $\left\lceil \frac{m}{2} \right\rceil$ $*$s.
Ana's idea is, until her last move, never to fill in any $*$, ensuring that Banana always erases at most
$s \leq \left\lfloor \frac{m}{2} \right\rfloor$ spaces.
Since $m > \left\lfloor \frac{m}{2} \right\rfloor$, Ana can choose $k=s+1\leq m$ on her next move, repaint all the cells that Banana erased,
and paint a new cell that is not a $*$.
When this is not possible, it's because Banana just erased $\leq \left\lfloor \frac{m}{2} \right\rfloor$ cells, and therefore there are no more than
$\underbrace{\left\lfloor \frac{m}{2} \right\rfloor}_{\text{Banana}} + \underbrace{\left\lceil \frac{m}{2} \right\rceil}_* = m$ erased cells.
Ana wins immediately.
MarcioCohen
31.10.2023 23:15
The answer is $88$. Approach: A. We find the maximum number $g(k)$ of greens that we can have while avoiding k consecutive greens. B. We find, for each k, a winning strategy for Ana that requires $m = m(k)$ C. We show that this function $m(k)$ is minimum for $k=45$, yielding $m(45) = 88$ as a possible $m$. D. We show that if $m \leq 87$, then Banana can prevent Ana from winning. A. Finding the maximum number $g(k)$ of greens that we can have while avoiding k consecutive greens: Divide $2024$ by $k$ and write $2024 = q \cdot k + r, 0 \leq r \leq k-1$, where $q = \left \lfloor \frac{2024}{k} \right \rfloor$, to group the positions $p_{1}; p_{2}; ...; p_{2024}$ as $$(1; 2; \cdots; k) \; (k+1; k+2; \cdots; 2k) \; (2k+1; \cdots; 3k) \; \cdots \; ((q-1)k+1; \cdots; qk) \; (qk+1; \cdots; qk + r)$$To avoid k consecutive 1s, we need to take at most $k-1$ from each of the first $q$ groups above and $r$ from the last group. And it is clear that by doing so we can achieve a configuration without $k$ consecutive 1s (simply avoid the last one in each k-group). Therefore, $$g(k) = q(k-1)+r = qk+r - q = 2024 - \left \lfloor \frac{2024}{k} \right \rfloor $$ B. Given k and a value $m(k)$ to be found, Ana can execute the following strategy: 1) Ana paints (turn green) all $p_{i} \equiv 1 \mod k$. She will turn $\left \lfloor \frac{2024}{k} \right \rfloor$ greens and Banana will be able to erase (paint white) at most 1 position. 2) Ana paints all $p_{i} \equiv 2 \mod k$ plus the one just deleted. She will turn $\left \lfloor \frac{2024}{k} \right \rfloor + 1$ greens and Banana will be able to erase at most 2 positions. 3) Ana paints all $p_{i} \equiv 3 \mod k$ plus (at most) 2 recently deleted. She will turn $\left \lfloor \frac{2024}{k} \right \rfloor + 2$ greens and Banana can then erase at most 3. 4) Ana paints all $p_{i} \equiv 4 \mod k$ plus (at most) 3 recently deleted. She will turn $\left \lfloor \frac{2024}{k} \right \rfloor + 3$ greens and Banana can then erase at most 4. $\cdots$ k) Ana paints all $p_{i} \equiv k \mod k$ in addition to the (at most) k-1 recently deleted. She will turn $\left \lfloor \frac{2024}{k} \right \rfloor + k - 1$ greens and win the game. This shows that Ana can win the game as long as $m(k) \geq \left \lfloor \frac{2024}{k} \right \rfloor + k - 1$ C. Now we minimize $m(k)$. On the one hand, we have $$m(k) \geq k + \frac{2024}{k} - 1 - 1 \geq 2\sqrt{2024} - 2 \Rightarrow m(k) \geq 88$$On the other hand, $m(45) = 45 + 44 - 1 = 88$, so the minimum possible $m$ is 88. In particular, this shows that there is a winning strategy for Ana when $m=88$. D. Finally, we show that for $m \leq 87$, Banana can prevent Ana from winning. In fact, if Banana gets G greens, then she can pick $k$ such that $g(k) < G \leq g(k+1)$ and find (from item A) $k$ greens to be erased. After that, Ana will always receive a number of whites at least equal to $$k + 2024 - G \geq k+2024-(2024-\left \lfloor \frac{2024}{k+1} \right \rfloor) = m(k+1) \geq 88$$Since Ana can only turn $87$ whites at a time, she can never win in this case.
trying_to_solve_br
04.12.2023 23:41
Here is another way of proving the bound: Look at the end of the game. If the greatest chain of greens at last is $x$, then notice that if $B$ takes off $x$, then $A$ has to paint $\lfloor \frac{2024}{x+1} \rfloor + x$ squares, because there are at least $\lfloor \frac{2024}{x+1} \rfloor$ white divisions. But notice that if $M= \lfloor \frac{2024}{x+1} \rfloor + x$, then $M+2=\lfloor \frac{2024}{x+1} \rfloor + x + 1 + 1 > \frac{2024}{x+1} + x + 1 \ge 2. \sqrt{2024} > 89.97$, thus $M > 87.97 \implies M \ge 88$. Then, if $A$ doesn't have $88$ or more, she looses.
bhan2025
27.12.2023 15:14
A 'block' is a sequence of consecutive green squares $m=88$ obviously works (just make $45$ green blocks of $44$ squares each) We will now prove the minimality of $88$. Assume $m$ works Let's say that, after Ana's second to last move, there were $k$ non-green squares. This means there were at most $k+1$ green blocks. Ana must win in her next move, meaning that regardless of which block Banana chooses to paint, the number of green blocks is at least $2024-m$. Since there were at most $k+1$ green blocks and $2024-k$ white squares, by PHP there is a block of at least length $\lceil \frac{2024-k}{k+1} \rceil$. Thus, we get the inequality $2024-k-\lceil \frac{2024-k}{k+1} \rceil \geq 2024-m$. By AM-GM, it is trivial that $LHS \leq 1936$ (the equality condition is $k = 44$) Thus, $2024-m \leq 1936 \implies m \geq 88$