Traveling Through a Square
Date: 11/25/2001 at 20:23:04 From: stephen Subject: Traveling through a square How do I get from the bottom left-hand corner of a 64-block square to the top right-hand corner, only going through each square once?
Date: 11/26/2001 at 11:36:51 From: Doctor Ian Subject: Re: Traveling through a square Hi Stephen, This is a pretty interesting question! Let's try looking at some small squares, to see if we can find some kind of pattern that we can apply to squares of any size. I'm assuming that you can cut across a corner. For example, I think this would be a legal way to move from the LL corner to the UR corner of a 2x2 square: +-+-+ |2|4| +-+-+ |1|3| +-+-+ For convenience, I'm not going to draw the borders of the squares from now on, so the figure above would look like 2 4 1 3 Now, for any NxN square, where N is odd, the answer is pretty easy - just go up and down the columns until you reach the end: 3 4 9 2 5 8 3x3 1 6 7 5 6 15 16 15 4 7 14 17 24 3 8 13 18 23 5x5 2 9 12 19 22 1 10 11 20 21 Unfortunately, in our case, N = 8, which is even. So the next thing we might try is this: Can we find a way to transform the problem into a different problem, where the solution is obvious? For example, suppose we have a 6x6 square: * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * We could 'cut off' the first three columns this way: 6 7 8 * * * 5 9 10 * * * 4 11 12 * * * 3 13 14 * * * 2 15 16 * * * 1 17 18 19 * * Now, what's left isn't a square... but we can still zip up and down the columns to get to the UR corner. Can you generalize this so that it works for an 8x8 square, or any other (even)x(even) square? - Doctor Ian, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum