There is a row of $100N$ sandwiches with ham. A boy and his cat play a game. In one action the boy eats the first sandwich from any end of the row. In one action the cat either eats the ham from one sandwich or does nothing. The boy performs 100 actions in each of his turns, and the cat makes only 1 action each turn; the boy starts first. The boy wins if the last sandwich he eats contains ham. Is it true that he can win for any positive integer $N{}$ no matter how the cat plays? Ivan Mitrofanov
Problem
Source: 42nd International Tournament of Towns, Senior A-Level P4, Spring 2021
Tags: combinatorics, game, Tournament of Towns
sn6dh
19.02.2023 13:52
What a nice problem!
The answer is no.
For convenience, let's call a sandwich hamful if the ham is not eaten; hamless otherwise.
Claim 1: Given $2M$ sandwiches numbered from $1$ to $2M$, in each round the boy does one action and then the cat. After $M$ rounds, the cat can assure that all $M$ uneaten sandwiches are hamless.
Proof:
It can be regarded as $2$ stacks containing $M$ hamful sandwiches. In each round, the boy chooses a stack and eats the top sandwich, and then the cat chooses any sandwich and eats the ham.
The strategy of the cat is: In each round, choose the stack that is not chosen by the boy in this round, and eat the ham of the bottom sandwich of this stack.
We can see that after each round, the number of hamful sandwiches in both stacks decrease by at most $1$, and the boy can eat a hamless sandwich in a stack only if he has eaten all hamful sandwiches in this stack.
$\because$ no number of hamful sandwiches in any stack decreases to $0$ before finishing the $M$-th round.
$\therefore$ in the first $M$ rounds, the boy can't eat any hamless sandwiches.
$\Rightarrow$ the $M$ uneaten sandwiches are hamless.
Claim 2: Given $2M\times100$ sandwiches numbered from $1$ to $200M$ and $r\in\{0, 1, \dots, 99\}$, after $M$ rounds, the cat can assure that all $M$ uneaten sandwiches with number $\equiv r\pmod{100}$ are hamless.
Proof:
In each round, since the uneaten sandwiches after the boy's turn are consecutive, there is exactly one toast with number $\equiv r\pmod{100}$ eaten by the boy.
$\Rightarrow$ take the $2M$ toasts with number $\equiv r\pmod{100}$, and it can be regarded as the same game in Claim 1, so the cat can assure it.
Take $N=2^{101}$, and after $2^{100}+2^{99}+\cdots+2^{101-k}$ rounds, the cat can assure that all $k2^{101-k}$ uneaten sandwiches with number $\equiv r\pmod{100}$ for all $r\in\{0, 1, \dots, k-1\}$ are hamless by doing Claim 2 $k$ times.
$\therefore$ for $k=100$, all of the $100$ uneaten sandwiches are hamless, and the boy loses.
CBMaster
28.08.2024 15:58
Similar idea to Indonesia LuMat final 2019_8.