Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/