Question 75
Given a $2n \times 2n$ table, a subset $S$ of its cells is called labyrinthine if it has the following properties:
- from every cell of $S$ it is possible to move to every other cell of $S$ moving only from cells of $S$ to adjacent cells of $S$ (horizontally or vertically, that is, having a side in common with the cell of origin);
- it is not possible, starting from a cell of $S$, to return to the same cell moving only to adjacent cells of $S$ and never crossing the same side twice.
a. Prove that if $S$ is labyrinthine then it cannot have more than $3n^{2}$ cells;
b. Exhibit a labyrinthine set of 12 cells for $n=2$.
c. We call perimeter of $S$ the number of sides adjacent to at least one cell of $S$, but not to two cells of $S$. If $S$ is labyrinthine and consists of $k$ cells, what is its perimeter?
d. Prove that there is no labyrinthine set of 300 cells if $n=10$.
- from every cell of $S$ it is possible to move to every other cell of $S$ moving only from cells of $S$ to adjacent cells of $S$ (horizontally or vertically, that is, having a side in common with the cell of origin);
- it is not possible, starting from a cell of $S$, to return to the same cell moving only to adjacent cells of $S$ and never crossing the same side twice.
a. Prove that if $S$ is labyrinthine then it cannot have more than $3n^{2}$ cells;
b. Exhibit a labyrinthine set of 12 cells for $n=2$.
c. We call perimeter of $S$ the number of sides adjacent to at least one cell of $S$, but not to two cells of $S$. If $S$ is labyrinthine and consists of $k$ cells, what is its perimeter?
d. Prove that there is no labyrinthine set of 300 cells if $n=10$.