Suppose a grid with $2m$ rows and $2n$ columns is given, where $m$ and $n$ are positive integers. You may place one pawn on any square of this grid, except the bottom left one or the top right one. After placing the pawn, a snail wants to undertake a journey on the grid. Starting from the bottom left square, it wants to visit every square exactly once, except the one with the pawn on it, which the snail wants to avoid. Moreover, it wants to finish in the top right square. It can only move horizontally or vertically on the grid. On which squares can you put the pawn for the snail to be able to finish its journey?
Problem
Source: Dutch IMO TST 2018 day 1 p1
Tags: combinatorics, grid
21.04.2021 00:00
We first color the squares of the grid in a chess board type fashion. The bottom left and top right corners have the same color (suppose black). 1) We shall first prove that for the journey to end, the pawn can't be on a black square. If it were the case then there are 2mn-2 black squares (2mn - the square on which we start - the square which the pawn sits) and 2mn white squares. But in order to get to a black square we must have been on a white square, so the number of black squares must be greater or equal to the number of white squares, and thus a contradiction. 2) Next we must show that for any placement of the pawn on a white square, the journey can end. (in the proof I will use matrix notation) We will proceed by strong induction over m and n. The base case is when either one of m and n are 1 which is trivial. Next we suppose that the conclusion is true for all pairs (a,b) with a from the set {1, 2,...,m} and b from {1,2,...,n} besides from (a,b)=(m,n), and prove it for a=m and b=n. If the pawn isn't in any of the entries ai,1 or ai,2 for i ranging from 1 to 2m, then the snail can walk in a straight line from a2m,i to a1,1, turn right to a1,2, walk in a straight line from there to a2m,2 and finally turn left to a2m,3 (he can go on that square since the pawn sits on white squares and a2m,3 is black). This way we have reduced the problem to the m, n-1 case which we assumed was true due to strong induction. We can use the same argument if the pawn wasn't in any of the squares a2m,i or a2m-1,i for i ranging from 1 to 2n. Thus we have the only case when the pawn sits in one of the squares a2m,2 or a2m-1,1 (remember the pawn sits only on white squares) and w.l.o.g. suppose it's a2m,2. Then the snail will take the following path: a2m,1, a1,1, a1,2, a2m-1,2, a2m-1,3, a2m,3, a2m,2n, a2m-1,2n, a2m-1,4, a2m-2,4, a2m-2,3. The catch is that now the parameters of the board have both decreased by 1, but the snail cannot pass through the entry a2m-2,4 like it was a pawn for a (2m-2)x(2n-2) board. This observation completes the proof by induction, and thus the entire solution.
26.03.2022 21:29
Basically the same. Let $a_{i,j}$ denote the square belonging to the $i$-th row, and $j$-th column. Let a square $a_{i,j}$ in the grid be white if$i+j\equiv 0\mod 2$. Let a square $a_{i,j}$ be black if $i+j\equiv 1\mod 2$. Clearly, there are $2mn$ squares of each color. Notice that whenever the snail makes a move from one square to another, the color of these squares must be different. Now, consider the sequence defined by all the squares through which the snail passes. This sequence has $4mn-1$ elements, as it doesn't pass through only one square of the grid. Also, the first and last squares of the sequence are white, so there must be $2mn$ white and $2mn-1$ black squares. This way, the square through which the snail doesn't pass must be black. Now, let's prove, by induction, that such square can be any black square. In the case $m=1$, or $n=1$, it is trivial. Suppose that, for a grid $2a\times 2b$, any black square can be removed, and the snail will finish its journey. Now, consider two new tiles: 1. $(2a+2)\times 2b$. Wherever the removed square is, either the top $2\times 2b$ block, or the bottom $2\times 2b$ block will not contain such square. Then, by the induction hypothesis, the snail can first cover a block $2a\times 2b$ containing the removed square, starting and finishing in two opposite corners. Then it just remains the snail to cover an entire block $2\times 2b$, starting by the bottom right corner, and finishing at the top right corner, which it can definitely do. 2. $2a\times (2b+2)$. It is analogous to 1. Therefore, by induction, any black square might be removed from any grid $2m\times 2n$, and the snail will be able to complete its journey.