Santa has to deliver Christmas presents to children in a town. The town is rectangular in shape and it can be divided into square regions. After the division, it looks like a grid with $101$ columns and infinitely many rows. Santa labeles the square regions with consecutive integers starting from $1$, so that the square on the $m^{th}$ row and $n^{th}$ column is labeled as $101m + n - 101$. Grinch hates Christmas, he plans to stop Santa by placing mischievous little monsters who love stealing Christmas presents in regions labeled with odd prime numbers. These regions are called “dangerous regions”. Those regions without monsters are called “safe regions”. Santa can move from one region to another region only if they share a common side. Suppose Santa wants to move from a dangerous region $p$ to another dangerous region $q$ (where $p$ and $q$ are odd primes), and he wants all the regions in between his way to be safe regions, is it always possible for Santa to do so? Prove your claim.
Problem
Source: 2024 IGMO Christmas Edition #5 International Gamma Mathematical Olympiad
Tags: combinatorics
03.02.2025 06:14
We claim it is always possible for Santa to move. Define a safe path as a path of squares $a_1,a_2,\dots,a_k$ s.t. $a_i$ and $a_{i+1}$ are adjacent regions, and $a_{i+1}$ is safe, for $1 \le i \le k-1$,. Also, call a safe square $k$ not in column $1$ good iff $k-1$ is safe. Claim: If $k$ is good and in column $m < 101$, there is a safe path from $k$ to another good square $n$ in column $m+1$. Proof: It suffices to show that there is a good path from $k$ to a square in column $m+1$ (as then the first square hit in column $m+1$ is good). If $k+1$ is safe, we have $k \rightarrow k+1$. Otherwise, say $k = p-1$, where $p$ is an odd prime. If $p = 3$, we have the safe path $$2 \rightarrow 1 \rightarrow 102 \rightarrow 203 \rightarrow 204 \rightarrow 205.$$ So, assume $p > 3$. As $2 \mid p +101$, $p+101$ is safe. So, if $p+100$ is safe, then we have $p-1 \rightarrow p+100 \rightarrow p+101$. So, assume $p+100$ is prime as well. Then, $3 \nmid p,p+100$, so $p \equiv 1 \pmod 3$. As $p-1$ is good, then $p-2$ is safe. As $2 \mid p+99$, $p+99$ is safe. As $3 \mid p+200$, $p+200$ is safe. As $2 \mid p+201$, $p+201$ is safe (and so $p+201$ is good). So, $p-1 \rightarrow p-2 \rightarrow p+99 \rightarrow p+200 \rightarrow p+201$ is a safe path. Suppose that we cannot have a safe path from $p+201$ to column $m+1$. By the same reasoning as above, $p+202 \equiv 1 \pmod{3}$, a contradiction. So, there is a safe path from $p+201$ to column $m+1$, and we're done. Claim: For an odd prime $p$ not in column $100,101$, one of $p+2,p+102,p+203$ is good, and there is a safe path from $p$ to that number. Proof: Note that $2 \mid p+1$, so $p+1$ is safe. If $p+2$ is safe, then $p+2$ is good, and we have $p \rightarrow p+1 \rightarrow p+2$, and we're done. Otherwise, assume $p+2 > 3$ is prime. As $2 \mid p+101$, we have $p+101$ is safe. If $p+102$ is safe, we have $p+102$ is good, and $p \rightarrow p+101 \rightarrow p+102$, and we're done. So, assume $p+102 > 3$ is prime. Then, $3 \nmid p+2,p+102$, so $p \equiv 2 \pmod 3$. Then, $3 \mid p + 202$. As $2 \mid p + 203$, then $p + 203$ is good, and we have $p \rightarrow p+101 \rightarrow p+ 202 \rightarrow p+203$, and we're done. Now, we will finish the question with these $2$ claims. To do this, we show there is a safe path from any odd prime $p$ to $202$. This finishes the question, as for odd primes $p,q$, we can go $p \rightarrow 202 \rightarrow q$, all being on safe squares. For an odd prime $p$ in column $101$, it must be $101$, so we can move up to $202$. For an odd prime $p$ in column $100$, it cannot be in row $1$, so moving right, we go to $101k$, where $k \ge 2$. Then, we may move down until we hit $202$. For any other odd prime $p$, from our second claim, we may find a safe path from $p$ to a good square $k$. By repeatedly using our first claim, we can extend this safe path to the next column, and do this until we hit column $101$. We cannot have hit $101$ (as this is a safe path), so we can go down until we hit $202$. We are done.