As we start into a new year, and start to anticipate all of the amazing new discoveries and scientific theories that will come with it, I was trying to think of a good subject for the first article of 2023. I considered writing reviews of leading edge artificial intelligence or quantum computing techniques, or perhaps a discussion of some of the latest theories in astrophysics or exotic particle physics. In the end though, I decided that coming out of the holidays we should go with a bit of light recreational mathematics instead.

About eight years ago I posted an article on the wire filling problem, alternately known as the greedy snake puzzle, and I ;eft the proof to the reader to work out, (As an aside and in answer to a few questions that I received, I do not claim to have invented this puzzle, but neither have I found any previous references to it,) 

Suppose that you have a rectangle of integer dimensions M x N, with a point/vertex located at every point in the exterior and perimeter whose coordinates are integers (ie (0,0),(1,0),(2,4)). Is there a path composed of horizontal and vertical unit length edges, which crosses each vertex exactly once, and with the added constraint that after the path changes directions or makes a turn, it must travel for at least two units before turning again.

At the time that I posted this, I stated that the answer was negative but I didn't bother to prove it since I thought that the proof would be quite simple. However since then a number of people have asked me for the proof, and one website even listed this as an unsolved problem (which is certainly is not).

So here we go...

The secret to this proof is to ignore the shape of the path, and calculate its length instead in two separate ways. The first method is to use the first constraint, namely that every vertex gets visited exactly once. There are (M+1)x(N+1) vertices, and aside from the initial vertex, each vertex is reached by adding one unit length to the path. Therefore

L = MxN + M+N

The second method uses the second constraint. Consider a unit square formed by four adjacent vertices. Because the path cannot make two turns close together, this square cannot have three or four edges in its boundary. Its boundary  will contribute at most only two edges to the path. Because this next step can be confusing at first, let us consider each step carefully:

- The total number of unit squares is MxN, and each square contributes a maximum of two units to the length. \Therefore L < 2 M x N

- Any edge that borders two squares will be counted twice. Therefore we must either subtract the number of interior edges, or alternatively add the number of perimeter edges np to the length and then divide by two.

- Because no vertex can be visited twice, the path cannot contain the entire perimeter, and therefore np is strictly less than the length of the perimeter. Or np < 2(N+M)

When these three conditions are combined, we have an upper limit on the length of the path:
.
L < MxN + N + M

And now we have the crux of the proof. Any path that visits every vertex once has length MxN+N+N, while any path that contains no sharp turns must be strictly less than this number. 

We have proven that any path that obeys both restrictions also obeys  L<  L and thus no such solution can exist. Thus it is proven.