9
$\begingroup$

We'll define a tour of some N x M grid as any sequence of tiles such that the first tile is the bottom left corner, any two consecutive tiles are adjacent, and every tile appears in the sequence exactly once. We'll call a tour tortuous if there is no set of four consecutive tiles in the tour that forms a 1 x 4 (or 4 x 1) rectangle.

For which N, M does there exist a tortuous tour?

Example (two tortuous tours of 4 x 5):

Example Tour 1enter image description here

$\endgroup$
  • 1
    $\begingroup$ I'm pretty sure you can construct a Hilbert-curve-like path for any rectangular mxn... $\endgroup$ – Joe Z. Jun 2 '16 at 1:34
  • $\begingroup$ @JoeZ. Hilbert curve solves $2^n \times 2^n$. $\endgroup$ – Ben Frankel Jun 2 '16 at 1:36
  • $\begingroup$ And $2^n \times 2^{n+1}$, if you glue two of them together. $\endgroup$ – Joe Z. Jun 2 '16 at 1:37
  • 1
    $\begingroup$ @JoeZ True, so you can get $2^n \times k\cdot2^n$ like that. $\endgroup$ – Ben Frankel Jun 2 '16 at 1:38
  • $\begingroup$ I don't know if you can get $k > 2$ in all cases. If you chain them side-by-side when $n$ is even, it creates segments of length 4. $\endgroup$ – Joe Z. Jun 2 '16 at 1:40
7
$\begingroup$

I believe this is possible for

All $M$ and $N$ with $M, N > 1$.

Here are the gadgets I need to prove it. Note that it doesn't matter which corner of the rectangle you start since you can always rotate the picture.

enter image description here

By using gadgets (1) and (2), you can essentially subtract 3 from the height of the grid. (1) works for grids of even width, and (2) works for grids of odd width (just add more up and downs for wider grids). Note that (1) only works on grids of width at least 8, and (2) works for grids of width at least 5.

After subtracting 3 from the height enough times, you'll be left with a grid of height 2, 3, or 4. If the grid is height 2, just zig-zag back and forth and fill in the rest of the grid. If it is of height 3, just repeat gadgets (1) or (2). If it is of height 4, then use gadget (3) for grids of odd width and gadget (4) for grids of even width.

This essentially takes care of all cases except $6 \times 6$. But this is possible too, as shown by gadget (5).

$\endgroup$
  • $\begingroup$ Great solution! Mine is not as simple. Very minor comment: technically, as defined, 1 x [1,2,3] are also possible. $\endgroup$ – Ben Frankel Jun 3 '16 at 1:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.