16 Squares and 5 Colors

Date: 08/15/2002 at 18:05:23
From: Dakota Dill
Subject: Puzzle math

You have 16 squares in a box, with 5 colors: 4 blue, 3 green, 3 red, 
3 white, and 3 black. The same colors can't touch or be in the same 
row.

I have tried everything, using markers and every way I can, and a 
color always touches.

Date: 08/15/2002 at 23:13:00
From: Doctor Peterson
Subject: Re: Puzzle math

Hi, Dakota.

Interesting puzzle! Let's try to find a way to organize our attempts, 
so we can be sure we've tried everything.

Since I don't see any obvious way to solve this, I'll start by just 
trying something. First, I'll need a way to show what I'm doing; 
rather than use colors, I'll call the five colors X, A, B, C, D, 
where there are 4 X's and 3 of each of the others:

    XXXX AAA BBB CCC DDD

Since there are four X's, and there can be no more than one in any 
row, there must be one in each row.

Let's start with the first row:

    X A B C    A X B C
    - - . .    - - - .
    - . . .    . - . .
    - . . .    . - . .

The X can go either at a corner or in the middle; and it doesn't 
matter which other colors we use, as long as they are all different, 
since there are the same number of each. (I haven't even said which 
color is which yet.) So these are really the only two ways to start.

I marked where the X can't go, because it would be in the same column 
or would touch. So there are only two places where the X could go in 
the next row for the left picture, and only one for the right 
picture. Let's place them, and mark where the next one can't be:

    X A B C    X A B C    A X B C
    - - X -    - - - X    - - - X
    - - - -    - - - -    . - - -
    - . - .    - - . -    . - . -

It's not hard to see where the other two X's have to go, is it?

Put those in place, then do some similar thinking about the other 
colors. But for them, we have to leave each color out of one row, and 
replace it with D, which has to be in three rows.

If you keep track of your thinking like this, then if you find that 
you can't solve the puzzle, you can instead prove that it CAN'T be 
done.

But I was able to solve it. One thing that helped was realizing that 
each of the four remaining colors had to be in the middle square. See 
what you can do!

Spoiler:  Here's the solution:
















    A X B C
    C D A X
    X B C D
    D A X B

Note the symmetry; A, B, C, and D all have the same pattern.


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