Finite version of fox in a hole

source

Fix some $n\in\mathbb{N}$ known to you and the fox. There is a hole numbered $i$ for every $i\in[n]$, and the fox is in one of them. Every morning you can check a hole and win if you catch the fox there. Otherwise that evening the fox moves from its hole $k$ to one of $\left\{k-1,k+1\right\}\cap[n]$. The process repeats indefinitely until the fox is caught. Do you have a strategy to catch it eventually, regardless of how it moves?

==============================================

Solution:

Lemma: if at some point the fox is at hole $k_1$ when we check hole $k_2$ where $k_1\le k_2$ have the same parity, then we will catch it in at most $k_2-2$ days if we check holes $k_2-1,k_2-2,\dots,2$ on subsequent days.

Checking holes $$2,2,3,4,\dots,n-2,n-1,n-1,n-2,n-3,\dots,3,2$$ suffices. Initial two checkings on hole $2$ makes sure that the fox is not in hole $1$, hence if it is not caught when hole $n-1$ is first checked, the fox's and your holes have different parity. The second check on hole $n-1$ serves two purposes: to make sure the fox's hole is not beyond yours, and to make both holes of same parity. Then, apply the lemma again after interchanging the role of holes $2$ and $n-1$ the fox will be caught by the time you check $2$.

Infinite version of fox in a hole

source

There is a hole numbered $n$ for every $n\in\mathbb{N}$, and a fox is in one of them. Every morning you can check a hole and win if you catch it there. Otherwise that evening the fox moves from its hole $k$ to one of $\left\{k-1,k+1\right\}\cap\mathbb{N}$. The process repeats indefinitely until the fox is caught. Do you have a strategy to catch it eventually, regardless of how it moves?

==============================================

Solution:

Lemma: if at some point the fox is at hole $k_1$ when we check hole $k_2$ where $k_1\le k_2$ have the same parity, then we will catch it in at most $k_2-2$ days if we check holes $k_2-1,k_2-2,\dots,2$ on subsequent days.

The overall strategy is this. For $n=1,2,\dots$, round $n$ consists of checking hole $2^{n+1}$ on day $$2^1-1+2^2-1+\dots+2^n-1=2^{n+1}-2-n,$$ and decreasing the hole index every following day until hole $2$ has been checked. Clearly for some $n$ the sufficient condition of the above lemma holds, so the fox will be caught on round $n$.

IMO 2026 Problem 4

Shan-Yu and Mulan are playing a game. Let $\theta$ be an angle with $0^\circ<\theta<180^\circ$ known to both players. Initially, Shan-Yu makes a paper triangle $\mathcal{T}$ with measurements of his choice. Then, they repeatedly perform the following steps:

If $\mathcal{T}$ has at least one angle measuring exactly $\theta$, then the game stops and Mulan wins.

Otherwise, Mulan chooses a point $P$ on the perimeter of $\mathcal{T}$, different from its three vertices. She then makes a straight cut from $P$ to the opposite vertex of $\mathcal{T}$, splitting it into two triangles.

Shan-Yu discards one of the two triangles. The remaining triangle becomes the new $\mathcal{T}$.

For which real values of $\theta$ can Mulan guarantee her victory in finitely many steps, no matter how Shan-Yu plays?

=============================================

The answer is $\boxed{\theta=\frac{\pi}{n},n\in\mathbb{N}\setminus\{1\}}$.

We say that an angle is good if it is an integer multiple of $\theta$. Clearly, Mulan can win if $\pi$ is good. Otherwise, Shan-Yu sets up $\mathcal{T}$ without any good angle. Consider the first time Mulan marks $P$ such that both triangle $ABP$ and $ACP$ has a good angle. By definition, none of $\angle B$ and $\angle C$ is a good.

- If both $\angle APB$ and $\angle APC$ are good, then so is $\pi$, a contradiction.

- If both $\angle APB$ and $PAC$ are good, then so is $\angle C$, a contradiction.

- If both $\angle APC$ and $PAB$ are good, then so is $\angle B$, a contradiction.

- If both $\angle PAB$ and $\angle PAC$ are good, then so is $\angle BAC$, a contradiction.

Hence, Shan-Yu can prevent Mulan from winning by always picking a remaining triangle without any good angle.

IMO 2026 Problem 1

There are $2026$ integers greater than $1$ written on a blackboard, not necessarily different. In a move, Confucius chooses two integers $m>1$ and $n>1$ from different places on the blackboard and replaces these two integers with

\[\gcd(m,n) \quad \text{ and } \quad  \frac{\mathrm{lcm}(m,n)}{\gcd(m,n)}.\]

He continues to make moves while it is possible to do so.

(a) Prove that, regardless of the choices of Confucius, after finitely many moves, exactly one integer $M$ on the blackboard is greater than $1$.

(b) Prove that the value of $M$ does not depend on the choices of Confucius.

============================================

(a) After a move on $m$ and $n$, their product changes from $mn$ to $\mathrm{lcm}(m,n)\le mn$. The equality holds if and only if $m$ and $n$ are coprime, or equivalently, one of the new numbers is $1$. Hence, the sum of $\prod_{i=1}^{2026}x_i$ and the size of multiset $\{x_i:x_i>1\}$ decreases strictly after every move. Since this number does not decrease indefinitely, at some points the process halts, i.e., at most a number greater than $1$ remains. It is impossible that both new numbers are $1$, so exactly one number greater than $1$ remains at the end.

(b) For every prime $p$ that divides an initial number, let its initial exponents be $$q_1(p),q_2(p),\dots,q_{2026}(p).$$ After a move on numbers with exponents $q_i(p)\le q_j(p)$, they become $$(q_i(p),q_j(p)-q_i(p)).$$ With the argument identical to the correctness proof of Euclean algorithm for computing GCD, it could be seen that the GCD of all these exponents do not change after a move. It is also clear that at the end exactly one nonzero exponent remains, which is $$\gcd\left(q_1(p),q_2(p),\dots,q_{2026}(p)\right).$$ Hence the remaining number is $$M=\prod_pp^{\gcd\left(q_1(p),q_2(p),\dots,q_{2026}(p)\right)}.$$

IMO 2026 Problem 3

Let $n$ be a positive integer. Alice and Bob have a stick of length $1$ and want to divide it between themselves. Alice marks at most $n$ points on the stick, and then Bob marks at most $n$ points on the stick. The marked points are distinct. Then, the stick is cut at all marked points, creating a number of pieces. Afterwards, they take turns claiming any unclaimed piece of the stick, with Alice going first. Each player's goal is to maximize the total length of their own pieces. For each $n$, determine the largest value $c$ such that Alice may guarantee a total length of at least $c$, regardless of Bob's play.

========================================

The answer is $\boxed{c=\frac{2^n}{2^{n+1}-1}}$.

Alice gets at least $\frac{2^n}{2^{n+1}-1}$:

Up to scaling factor $\frac{1}{2^{n+1}-1}$, Alice makes $n+1$ segments of lengths $1,2,4,\dots,2^n$. At least one of them is not further split by Bob. Regardless of how Bob plays, Alice gets at least half of $2^n,2^{n-1},\dots,2^{k+1}$, and the entire $2^k$. Hence Alice gets at least $2^n$, which we further divide by $2^{n+1}-1$.

Bob gets at least $\frac{2^n-1}{2^{n+1}-1}$:

Let the lengths of the $n+1$ segments made by Alice be $\ell_1,\dots,\ell_{n+1}$. If any of them is $0$, then Bob splits every segment into two equal halves and gets at least $\frac{1}{2}$. Otherwise, we claim that Bob gets at least $\frac{1-e}{2}$ where $$e=\min_{A,B\subseteq [n+1],A\ne B}\big|\sum_{i\in A}\ell_i-\sum_{i\in B}\ell_i\big|.$$ We make $A$ and $B$ disjoint by removing common elements. Say $|A|=a$ and $|B|=b$. There are exactly $n+1-a-b$ segments outside of $A\cup B$. Bob cuts once to get $e$, cuts $a-1+b-1$ times to get pairs of equal-lengthed segments, and then cuts $n+1-a-b$ times to split all other segments into two equal halves. Later Bob misses a segment of length at most $e$.

We have $e\le\frac{1}{2^{n+1}-1}$ because the multiset $L=\left\{\sum_{i\in A}\ell_i:A\subseteq[n+1]\right\}\subset[0,1]$ of size $2^{n+1}$ has two elements that differ by at most $\frac{1}{2^{n+1}-1}$. Hence, Bob gets at least $$\frac{1-e}{2}=\frac{2^n-1}{2^{n+1}-1}.$$