Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Discrete Mathematics
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search