Little math problems July 2019

[Jim Horn]

My pleasure. As a first approximation, the total distance should approach a constant times the size cubed, as the number of cells approaches the size squared and the average distance to each approaches the size. Multiplied, that gives you the size cubed.

The distance for each cell is two identical distances, namely out and back. We can simplify by just counting one and doubling.

Similarly, each n x n square consists of four (n-1)/2 x (n+1)/2 areas that cover the square without overlap and only leave out the central square, for which no travel is needed. So if we find the distance out to each square in one area, we can multiply the sum of those by 8 to get the final number. Only having to count 1/8th of the steps makes doing so faster, easier and less error prone!

It's a quick task to do that for squares of size 1, 3, 5, 7 and 9. Then do a polynomial fit to that and you find that indeed, the coefficients are 0, 1, 0, -1 and 0, giving you x^3 - x, as mentioned.

In doing the area distances mentioned two paragraphs above, I noticed a simple recurrence relation that gave the total distance for any given size from the total of the next smaller size. Dropping that into the above polynomial gives the same result, confirming its validity.

Way back in the 1960s, Martin Gardner's "Mathematical Games" column in Scientific American (and one of his marvelous books) discussed the Calculus of Finite Differences. It's a simple and very effective tool for diving into many problems like this and finding their general solutions.

I suspect the same approach can be used to find the total distance if diagonal paths are allowed if the diagonals are limited to 45 degree ones. For any diagonal (i.e. straight line from center cell to any other), I suspect this won't give exact results but may help with a sufficient approximation. Anyone want to give it a try?