Checkerboard Pattern Using an L Shape

Date: 10/14/2002 at 10:50:57
From: chris mills
Subject: Checkerboard Pattern - Using an L Shape


My co-worker and I have been working on his son's homework the last 
day or so.

Take an 8x8 checkerboard. Using the numbers 1-64, place the numbers in
any order so that numbers in an L shape (start point - 1 down - 1 to
the right) always add up to an odd number:

1
2 4
  3 6
    7 8

Using 1-64 as your number set, can you always get an L shape with the 
sum of the 3 digits as odd using up all the available "squares" on 
the board?

Date: 10/14/2002 at 12:13:56
From: Doctor Peterson
Subject: Re: Checkerboard Pattern - Using an L Shape

Hi, Chris.

I assume your co-worker's son has been working on this too!

The first thing I see is that we can ignore the specific numbers to 
start with, and just focus on the location of even and odd numbers. 
I'll represent even numbers by 0 and odd numbers by 1; then we need 
to fill a square with an equal number of 0's and 1's, since 1 through 
64 is split evenly.

Since a sum of three numbers will be odd either when one of them is 
odd, or when all three are odd, there are four configurations possible 
for each L:

    1      1      0      0
    1 1    0 0    1 0    0 1

I played with this for a while to see whether there are any obvious 
patterns. Starting at the lower left, for example, if we start with 
three odds, we have a choice of putting an odd number or an even 
number on top, and that forces all the remaining numbers in the 
diagonal:

    1      <-- this can be 1 or 0
    1 1    <-- this has to be 1, so we have three 1's
    1 1 1  <-- then this has to be 1, too

    0
    1 0    <-- this has to be 0, so we have one 1
    1 1 0  <-- and so does this

So we can either continue with all odds forever (which isn't good), 
or put in a row of evens eventually:

    0
    1 0
    1 1 0
    1 1 1 0
    1 1 1 1 0

The next row might start with an even or an odd, again:

    1  <-- a 1 forces an alternating diagonal
    0 0
    1 0 1
    1 1 0 0
    1 1 1 0 1
    1 1 1 1 0 0

    0  <-- and so does a 0
    0 1
    1 0 0
    1 1 0 1
    1 1 1 0 0
    1 1 1 1 0 1

All this playing didn't show me any obvious quick route to an answer, 
so I just tried building a square this way, always trying to keep it 
about half odd. After a couple of tries, I found a solution, which 
starts with three odds. To make the final answer, of course, we just 
have to go through and replace each 0 with an even number and each 1 
with an odd number.

If you have any further questions, feel free to write back.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 10/14/2002 at 12:32:32
From: chris mills
Subject: Thank you (Checkerboard Pattern - Using an L Shape)

Thank you. We literally just minutes ago found a solution, though we
started in the lower right corner.  I'm sure there are numerous
solutions but we were getting lost in our own cleverness.

We finally (as you started) just eliminated numbers and went with E's
and O's.  What took you an hour or so took us MANY hours.

Thanks for keeping our egos to a minimum :)