Problem 2065

Solution:

a. First of all we observe that a $2 \times 2$ square inside the grid can contain at most 3 cells belonging to the set $S$: indeed, if for contradiction there were a $2 \times 2$ square with all 4 cells belonging to the set $S$, then one could find a path, entirely contained inside the square, that contradicts the second condition given by the problem (for example, starting from the bottom-left cell of the square and going once right, once up, once left and once down one would return to the starting cell without ever crossing the same side twice).
Let us divide the whole grid into $n^{2}$ squares, each of size $2 \times 2$. By what was said before, each of these $2 \times 2$ squares can contain at most 3 cells belonging to the set $S$ and hence the set $S$ can contain at most $3 \cdot n^{2}$ cells.

b. An example of a mazy set of 12 cells in a $4 \times 4$ grid is given by the set of shaded cells in the following figure:

c. We prove by induction on the number of cells that if a mazy set $S$ has $k$ cells, then there are $2k+2$ sides adjacent to exactly one cell of $S$, that is
$$\operatorname{perimetro}(S)=2k+2 \text{.}$$
If $k=1$, then $S=4=2 \cdot 1+2$, as we wanted.
Let us now assume that the statement holds for any mazy set with $k-1$ cells, with $k \geq 2$, and let us consider $S$ a mazy set with $k$ cells.
All the cells of $S$ are adjacent to at least one other cell of $S$: indeed, given a cell $x$ of $S$, there exists at least one other cell $x'$ of $S$ distinct from $x$ ($S$ by hypothesis has at least two cells); by the first condition on mazy sets, it is possible to move from $x$ to $x'$ moving only from cells of $S$ to adjacent cells of $S$. In particular, there exists at least one cell adjacent to $x$.
There exists at least one cell of $S$ adjacent to only one other cell of $S$: assume for contradiction that there are no cells of $S$ with this property, that is, that all cells of $S$ are adjacent to at least 2 other cells of $S$; let $x_{0}$ and $x_{1}$ be two cells adjacent to each other and let us construct recursively the sequence of cells $x_{0}, x_{1}, x_{2}, \ldots$ in $S$, such that, for every $i \geq 1$, the cells $x_{i}$ and $x_{i+1}$ are adjacent and $x_{i+1}$ is distinct from $x_{i-1}$ (since every cell of $S$ is adjacent to at least two other cells of $S$, given $x_{i-1}$ and $x_{i}$, it is always possible to choose an $x_{i+1}$ that satisfies the required conditions). Let $t$ be the first time at which the sequence passes again over an already visited cell, that is, such that $x_{s}=x_{t}$ for some $s<t$; this leads to a contradiction, since the sequence $x_{s}, \ldots, x_{t}$ contradicts the second hypothesis on mazy sets. Hence there must exist at least one cell of $S$ that is adjacent to only one cell of $S$; let us call $c$ such a cell.
It is now immediate to verify that the set $S'$ formed by all the cells of $S$ minus the cell $c$, is still mazy. Since $S$ is obtained from $S'$ by adding the cell $c$, the set of sides adjacent to exactly one cell of $S$ is given by the set of sides adjacent to exactly one cell of $S'$, minus the side between $c$ and $S'$, and adding the other three sides of $c$, whence
$$\operatorname{perimetro}(S)=\operatorname{perimetro}(S')+2=(2(k-1)+2)+2=2k+2 \text{,}$$
where the second equality holds by the inductive hypothesis.

Second solution:
We want to prove that the set $S$ can be constructed recursively by attaching one cell at a time, in such a way that each attached cell is adjacent to exactly one of the previously attached cells; furthermore, we want to prove that every time a cell is attached, the perimeter increases by 2 with respect to the previous step.
Let $x_{1}$ be an arbitrary cell of $S$ and let $S_{1}$ be the set formed by the cell $x_{1}$, whose perimeter equals 4. If $k=1$, then we are done. If $k>1$, then the set $S$ contains at least one other cell $c$. Thanks to the first condition of mazy sets, we know that it is possible to reach $c$ starting from $x_{0}$ and moving only through adjacent cells; in particular, there exists at least one cell $x_{2}$ adjacent to $x_{1}$; let us call $S_{2}$ the set consisting of the cells $x_{1}$ and $x_{2}$ and observe that the perimeter of $S_{2}$ is $6=4+2$.
Suppose now that we have constructed the set $S_{j}$ with the rules stated above and let us call $x_{2}, \ldots, x_{j}$ the cells that have been attached in order to obtain $S_{j}$; if $j=k$, then $S=S_{k}$ and we are done. If $j<k$, then there exists at least one cell $c'$ in $S$ that is not in $S_{j}$ and, by the first condition of mazy sets, there exists a path of adjacent cells starting from $x_{0}$ and arriving at $c'$; let $x_{j+1}$ be the first cell traversed by this path that is not in $S_{j}$: in this way $x_{j+1}$ is adjacent to the cell that precedes it in the path, which is indeed a cell of $S_{j}$. Now we want to prove that $x_{j+1}$ is adjacent to a unique cell of $S_{j}$: suppose for contradiction that $x_{r}$ and $x_{s}$ are two cells of $S_{j}$ adjacent to $x_{j+1}$; then there exists at least one path completely contained in $S_{j}$ going from $x_{s}$ to $x_{r}$ that crosses only adjacent cells (indeed, by construction of $S_{j}$, there exist two paths, $\Sigma_{1}$ going from $x_{1}$ to $x_{r}$ and $\Sigma_{2}$ going from $x_{1}$ to $x_{s}$, that cross only adjacent cells; by traversing $\Sigma_{1}$ backwards and then $\Sigma_{2}$, one obtains the desired path). Let $\Sigma$ be the minimal path from $x_{r}$ to $x_{s}$ (that is, crossing the smallest possible number of cells) that crosses only adjacent cells and that is completely contained in $S_{j}$; by minimality, this path can never cross the same side twice (otherwise the path could be shortened). Now, starting from $x_{j+1}$, going to $x_{r}$, traversing $\Sigma$ until arriving at $x_{s}$ and finally returning to $x_{j+1}$, one finds a path completely contained in $S$ that crosses only adjacent cells and that never passes twice over the same side. We have thus found a contradiction to the second hypothesis of the problem and we have thus proved that $x_{j+1}$ can be adjacent to at most one cell of $S_{j}$.
Let $S_{j+1}$ be the set obtained by adding to $S_{j}$ the cell $x_{j+1}$. Observe that the set of sides adjacent to only one cell of $S_{j+1}$ is given by the set of sides adjacent to only one cell of $S_{j}$, from which we remove the side between $x_{j+1}$ and $S_{j}$ and to which we add the other 3 sides of $x_{j+1}$. From this it follows that every time we attach a cell, we add exactly 2 sides to the perimeter.
Since the perimeter of $S_{1}$ is 4 and to this exactly $k-1$ cells are attached in order to obtain $S_{k}=S$, we have
$$\operatorname{perimetro}(S)=4+2\cdot(k-1)=2k+2 \text{.}$$

d. Suppose that there exists a mazy set $S$ of 300 cells in a $20 \times 20$ grid. The perimeter of the whole grid is 80, while by the previous point we know that the perimeter of $S$ is $2 \cdot 300+2=602$.
Let $T$ be the set formed by the 100 cells that do not belong to $S$; observe that the perimeter of $T$ is at most $4 \cdot 100=400$ (that is, each cell of $T$ contributes at most 4 sides to the perimeter), while the perimeter of the whole grid is 80.
Since by definition a side contributes to the perimeter of $S$ only if it is adjacent to only one cell in $S$, we have that this side must either belong to the boundary of the grid, or be adjacent to a cell of $T$, whence
$$602=\operatorname{perimetro}(S) \leq \operatorname{perimetro}(T)+\text{ perimetro(Tabella) } \leq 400+80=480$$
which gives a contradiction.

Second solution:
Thanks to the previous point, we know that the set $S$ has a perimeter of 602 cells; moreover, again from the proof of the previous point, we see that every time a cell is attached, exactly one side is used to attach the cell to the set. Hence the number of sides that are adjacent to two cells of $S$ is exactly $300-1=299$ (one side for each attached cell). Hence the existence of $S$ requires at least $602+299=901$ sides. Since the grid possesses in total 840 sides, the set $S$ cannot exist.