Diagonal/Non-diagonal Grid Filling

[Dion Gijswijt]

Dear Leroy,

> Which grids are possible to fill in completely, however, if the path is
> not allowed to cross itself?

that is a nice puzzle!

The only square that can be filled completely is the 2x2 square (see below).

I think however that the infinite grid (rows and columns indexed by the
natural numbers) CAN be filled with a noncrossing path starting at the
upper left corner. I have no proof though. The paths seem to be quite
`wild'.

Also I think that I have seen this (or something very related) somewhere,
maybe in one of Gardners recreations... Does anyone know a reference?
Thanks!

Dion Gijswijt.

-----------------

Consider an nxm grid, with n,m at least 3. Suppose that there is a path
using all points of the grid (exactly once), that uses alternatingly
(horiz/vert) and diagonal edges and has no crossing edges.


Proof:

First suppose that there is a `border' (i.e. first/last row/column) that
does not contain an endpoint of the path.
Then each of the points on the border must be in a diagonal edge of the
path (since they are entered and left by the path). But that is clearly
impossible, since crossing edges are not allowed.

So the two endpoints of the path must be opposite corners of the grid, say
upper left and lower right.
Then the remaining (n-1) points on the left column are all in a diagonal
edge, and there is only one way to do this: these (n-1) diagonal edges
must all have direction `/'.
Similarly the (n-1) remaining points on the upper row must all be in
diagonal edges of direction `/'.
But then the diagonal edges through the point two places under the
upperleft corner and through the point two places at the right of this
corner overlap. A contradiction.



> I have a simple proof that shows that any grid of (2n)-by-(2n) can be
> filled in completely, assuming that the path is allowed to cross itself
> (which it can only do on diagonal sections).
>
> It can be best illustrated with an example:
> (For n = 8)
>
> 1  2 17 18 33 34 49 50
> 3 16 19 32 35 48 51 64
> 4 15 20 31 36 47 52 63
> 14 5 30 21 46 37 62 53
> 13 6 29 22 45 38 61 54
> 7 12 23 28 39 44 55 60
> 8 11 24 27 40 43 56 59
> 10 9 26 25 42 41 58 57
> thanks,
> Leroy Quet