Wikipedia:Reference desk/Archives/Mathematics/2015 November 11

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

November 11

Infinite Open Knights Tour coverage.

Resolved

After looking at the page Knight's Tour the following question occurs to me. Is there are method of creating a single specific infinitely spreading knight's tour "T" such that for any set of squares that eventually all of the squares in T will have been visited (and some number outside of T)? I know that for any square of size 5x5 or larger a tour can be picked, but, for example, a specific tour for a 11x11 board may not be able to be extended to cover a 13x13 board around it if the start and end points aren't within reach of the border, and even if they are, is there a guarantee that the outer ring can be covered if you can go beyond the 13x13.Naraht (talk) 00:04, 11 November 2015 (UTC)

It would be sufficient to show that for some n≥5, the following condition holds:

For each starting square on one side of an nxn board there exists tours ending on each of the other three sides.

Then the plane could be partitioned into nxn boards and walked board-to-board in a outward spiraling "King's tour" fashion.

I'd expect this condition to hold for some small n, and will write some code to search for it if I get a bit free time this weekend. -- ToE 13:12, 12 November 2015 (UTC)

Really good idea, but it doesn't quite work since the end square for one nxn board is *not* the starting square for the other. If you proved that for a 99x99 board, that you could start a tour in position 5/95 on each side and come out on position 5/95 on the other side, that wouldn't be enough, you'd need to instead figure out how to work from either position 2/8/92/98 on the other board. However for an odd n board, you only have have an open tour in the color that has one more than the other, so there wouldn't be a tour starting with an even number side position. So n has to be even. So this could be done if for an even numbered board, there existed an open tour that went from each of the one of the middle 4 squares on each side to a square of the other color (since an open tour on an even board will end with the other color) in the center of the other sides. So on a 6x6 board numbered across then down with a black square in the upper left, you need to have an open tour from ((3 to 7 or 3 to 19) and (3 to 33 or 3 to 35) and (3 to 18 or 3 to 30)) and ((5 to 7 or 5 to 19) and (5 to 33 or 5 to 35) and (5 to 18 or 5 to 30)).Naraht (talk) 17:51, 12 November 2015 (UTC)

I need more time to parse your objection, but consider this single tour on a 5x5 board:

18   3  12   7 [24]
11   6  17   2  13 
16  19   4  23   8 
 5  10  21  14   1 
20  15  [0]  9  22 

Thus you can enter a 5x5 sub-board in the middle of an edge and finish in a corner on the opposite edge. From there you can enter the middle of the edge of the next 5x5 sub-board whether it is continuing in the same direction or turning the corner of the outward spiral. -- ToE 18:44, 12 November 2015 (UTC)

Note that ToE specified that a path must be found "for each" square on the side of the board, not just for one square. So it doesn't matter where the tour ends - after one tour is completed, the knight moves to any square on the side of the next board, and continues from there (since there is a tour for every starting square). -- Meni Rosenfeld (talk) 19:59, 12 November 2015 (UTC)

That looks cool. The issue that I had was in regard to that the entry square (middle) didn't correspond to the exit square, but for the example given, the next step after 24 will be to the middle of the next box side on the one of the sides or across. Beautiful!Naraht (talk) 01:02, 13 November 2015 (UTC)

I should have been clearer that my sufficiency condition above was intended to ensure that whatever edge square a tile was entered on, there exists a tour that ends on the edge adjacent to the next tile, from which that next tile can be entered on some square of its adjacent edge. That was the lazy way of doing it, showing that some tour exists without specifying the actual connections, whereas the 5x5 center of edge to far corner tour, along with its rotations, gives a specific path.

As you pointed out, my sufficiency condition doesn't work for odd n, but my intuition that it would be met for small n proved true, as the following tours, along with their reflections (including across the diagonal for the first one), satisfy the condition for n=6.

[35] 30  21  18   3  28     8  29  22  33  10 [35]   24  29  32  15  18   3   [35] 22  27  10  33  20     9  22  17  30  15  24 
 22  17   2  29   8  19    21  32   9   2  23  12    33  14  25   2  31  16    26  11  34  21   2   9    18  31   8  23   2  29 
 31  34  23  20  27   4    28   7  30  11  34   3    28  23  30  17   4  19    23  28  25   8  19  32    21  10  19  16  25  14 
 16   1  32   7  12   9    31  20   1  24  13  16    13  34   1  26   7  10    12   7  30   1  16   3    32   7  12   1  28   3 
 33  24  11  14   5  26     6  27  18  15   4  25    22  27  12   9  20   5    29  24   5  14  31  18    11  20   5  34  13  26 
 [0] 15   6  25  10  13    19  [0]  5  26  17  14   [35] [0] 21   6  11   8     6  13  [0] 17   4  15     6  33  [0] 27   4 [35]

-- ToE 15:41, 13 November 2015 (UTC)

Pretty! but I don't think the first three are needed. If you are always leaving a box with the last entry in the corner, then which ever way you go, the first entry in the new square is in the middle 2 of the next square. So #4 and #5 (and their reflections) should be enough.Naraht (talk) 16:01, 13 November 2015 (UTC)

Right you are. Those two will do, in the same sense as the one 5x5. My original sufficiency condition was just to prove the existence of some path between tiles, without determining the specific ones which would be used. -- ToE 19:28, 13 November 2015 (UTC)

Yup. Sometimes you don't need all of the tools, but they can lead to more interesting questions. :)Naraht (talk) 20:15, 13 November 2015 (UTC)

Not to spoil anyone's fun, but here's a solution (based on adding 2-square borders, not tiling). -- BenRG (talk) 20:32, 12 November 2015 (UTC)

Cool! And the page http://demonstrations.wolfram.com/AnInfiniteKnightsTour/ shows an example with four rings to make it clear you can continue it forever.Naraht (talk) 01:02, 13 November 2015 (UTC)

Thank you for all of the help! Two *completely* different solutions!Naraht (talk) 01:02, 13 November 2015 (UTC)