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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.