Pieces on a Chess Board

Date: 10/27/96 at 6:55:43
From: Van Giai Ho
Subject: Chess board

Hello,
	
I've read some of the problems you have solved for other people and I 
am wondering if you can solve this problem for me:
 
Prove that with 9 separate playing pieces, you cannot place the pieces
on an 8 by 8 chess board such that the distance between any 2 pieces 
is always different.
		
I appreciate your help,
Hai Trung Ho

Date: 10/27/96 at 22:31:26
From: Doctor Dennis
Subject: Re: Chess board

This is a fairly tricky problem which makes use of something called 
the pigeonhole principle. The pigeonhole priciple, in its simplest 
form, says that if you have n+1 balls and you are trying to put them 
into n boxes, then at least two balls must go into the same box.

First, consider the number of different pairs of pieces there are 
given that there are 9 pieces. The first piece can pair off with each 
of the other 8 pieces. The second piece can pair off with the 7 other 
pieces since it has already been paired with the first piece. The 
third piece can pair off with 6 other pieces, since it has already 
paired off with the first two. etc.

There are 8+7+6+5+4+3+2+1 = 36 pairs

As a simple illustration of this, look at how many pairs of the 
letters a, b, c, d  there are. The pairs are:

     ab ac ad 3
     bc bd    2
     cd       1
     ----------
              6

Of course, the order of the pieces in the pair does not matter, since
the distance between piece 1 and piece 2 is the same as the distance 
between piece 2 and piece 1. This is why in the example we only need 
to count ac and not ca as well.

Next, let us consider the number of possible distances on the chess 
board. If we place one piece in a corner, there are 35 possible 
non-zero distances between it and another piece somewhere on the board

   *
   1  2
   3  4  5
   6  7  8  9
  10 11 12 13 14
  15 16 17 18 19 20
  21 22 23 24 25 26 27 
  28 29 30 31 32 33 34 35

So to arrange 9 pieces in the indicated manner, we would have to be
able to put 36 pigeons (distances between pairs of pieces) into only
35 holes (possible distances on the board).  

By the pigeonhole principle, at least 2 pairs of pieces must be the same 
distance apart. 

I hope this makes sense. It is a pretty high-level problem. Please 
write if you have more questions.

-Doctor Dennis,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/