3
$\begingroup$

Consider the following approach to constructing a maze: Create a rectangular grid of identical square tiles, each colored by one of N colors on a color wheel. For any pair of adjacent tiles, there is a wall between them if and only if their colors are not adjacent (or equal) on the color wheel.

For sufficiently large N, is it possible to create arbitrary configurations of walls using this scheme?

Several special cases are easy to solve:

Single Row: If your rectangular grid is a single row of tiles, then you can create any wall configuration using two non-adjacent colors. Fill in colors going from left to right. Any time there should not be a wall, place the same color as the tile to the left. When there should be a wall, place the other color.

2x2 mazes I was also able to construct all 16 possible wall configurations for a 2x2 grid.

Improve this question
$\endgroup$
4
  • $\begingroup$ Just to formalize what I mean by the colors on the color wheel, this problem is equivalent: tiles are labeled by integers in $\{1, ..., N\}$ and there is a wall between adjacent tiles with labels $l_1$ and $l_2$ if $|l_1 - l_2| \not \in \{0, 1, N-1\}$. $\endgroup$
    – Travis
    Commented Dec 1, 2023 at 21:15
  • $\begingroup$ A color is considered to be adjacent to itself? $\endgroup$
    – Gerry Myerson
    Commented Dec 1, 2023 at 23:51
  • 1
    $\begingroup$ Yes, sorry that was unclear! $\endgroup$
    – Travis
    Commented Dec 2, 2023 at 16:10
  • $\begingroup$ A potentially useful observation is that whenever you have a sequence of adjacent tiles A, B, and C, then if the colors of A and C are not two hops apart on the color wheel, then it is not possible to achieve all possible combinations of 4 walls around tile B. In particular, if A and C are both the same color, then the walls between B and tiles A and C are either both present or both missing. If A and C are more than 2 colors apart, it is impossible to have both walls be missing. $\endgroup$
    – Travis
    Commented Dec 2, 2023 at 16:26

1 Answer 1

Reset to default
4
$\begingroup$

If N is large enough, then the answer is no, since this maze can't be created:

      ._._._._._._.
  ._._| ._._. ._. |_.
._| ._. |_. ._. ._. |
| ._. ._. ._. ._._| |
| |_._. ._. ._. ._._|
|_._._._._._._._|

By "large enough", I just mean large enough that wrapping all the way around the color wheel can't possibly occur in the maze above - so N bigger than 50 is certainly large enough. This maze might also be a counterexample for small N, but I haven't found an easy way to check that.

The reasoning is as follows. If there is no wrapping around, then we may as well imagine that we are coloring the tiles by integers. Imagine, for the sake of contradiction, that there was a coloring of the tiles by integers satisfying your conditions.

For each wall, we keep track of which direction we need to cross the wall in order to cause the color to increase.

As we cross any wall in the increasing direction, the color must increase by at least $2$, and as we step from a tile to a neighboring tile with no wall between them, the color can decrease by at most $1$. So if I manage to draw a loop through the maze which is allowed to cross walls only in the increasing directions, and if the number of steps in my loop which don't cross walls is less than twice the number of steps which do cross walls (in the increasing directions), then I get a contradiction.

By drawing loops of length four, I can argue that in the configuration

. . .
._._.
. . .

the increasing direction for both walls must be the same, and in the configuration

. . .
. ._.
. | .

if the increasing direction for the top wall is upward, then the increasing direction for the left wall must be leftward (and similarly if we reverse the directions). Putting rotated versions of these facts together, we see that in the configuration

. . . .
. ._. .
._._| .
. . . .

the top wall's increasing direction must be the opposite of the bottom wall's increasing direction.

By drawing loops of length eight, we can also see that in every copy of the configuration

. . . .
._. ._.
. ._. .
. . . .

the top two walls must have the same increasing direction.

By finding copies of these configurations in the maze that I claimed couldn't be created, we can relate almost all of the increasing directions to each other, and we find that the increasing directions of the horizontal walls are either upward for odd y-coordinates and downward for even y-coordinates, or vice-versa. But then we have a loop of length 10 through a sub-configuration which looks like

 ._._.
 ._. .
 . ._.
 ._. .
 . ._.
 ._._.

which passes through 4 walls in their increasing directions, showing that no coloring is compatible with this choice of increasing directions.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you, this is a very interesting argument. The observation about closed loops is nice, and using it both to argue that certain walls must have related rising directions and then to construct a path of only rising directions with too few non-walls for contradiction is very nice. It's also surprising to me that the easier case to prove (at least by this argument) is when N is large, since my intuition suggested that for small N you may be forced into contradictions more quickly than if you had many colors at your dispoal. $\endgroup$
    – Travis
    Commented Dec 2, 2023 at 19:57
  • $\begingroup$ The motivation for the closed loops is this: if you have a system of inequalities of the form $x_i \le x_j + c$ for various constants $c$, then the system will be inconsistent iff there is a closed loop so that the sum of the constants which occur is negative. (This is true whether we are solving the inequalities over the rationals or the integers.) $\endgroup$
    – zeb
    Commented Dec 2, 2023 at 20:08
  • $\begingroup$ So in my mind, I was dividing the problem into an easy part and a complex part: the easy part was determining whether the inequalities have a solution once I know the increasing directions, while the complex part was determining the increasing directions. $\endgroup$
    – zeb
    Commented Dec 2, 2023 at 20:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .