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

### 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/
```
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

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/