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

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ I'm pretty sure you can construct a Hilbert-curve-like path for any rectangular mxn... $\endgroup$
    – user88
    Jun 2, 2016 at 1:34
  • $\begingroup$ @JoeZ. Hilbert curve solves $2^n \times 2^n$. $\endgroup$
    – Ben Frankel
    Jun 2, 2016 at 1:36
  • $\begingroup$ And $2^n \times 2^{n+1}$, if you glue two of them together. $\endgroup$
    – user88
    Jun 2, 2016 at 1:37
  • 1
    $\begingroup$ @JoeZ True, so you can get $2^n \times k\cdot2^n$ like that. $\endgroup$
    – Ben Frankel
    Jun 2, 2016 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$
    – user88
    Jun 2, 2016 at 1:40

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$
1
  • $\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, 2016 at 1:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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