16 checkers are placed on an 8 by 8 checkerboard, no two checkers on the same square. Show that some four of the 16 checkers are on the vertices of a parallelogram with positive area.

This can be viewed as a combinatorics problem.  I haven't solved it yet, but I think the solution lies in counting the squares.

Example:
Put checkers on 3 squares, there is one square that would make a parallelogram, so you can't put a checker on that one.  So we've used 3 checkers, 1 square is unavailable, and there are 60 open squares left.

Say we've put down 6 checkers.  There are 6 choose 3 (ie 20) ways to pick 3 of these 6 checkers.  For each of these there is one square that would make a parallelogram if we put a checker on it.  So now we have used 6 checkers, there are 20 squares we can't use, and there are 38 squares still available for the next 10 checkers.

As we add more checkers, there will be some of the disallowed squares that will be counted more than once, since more than one set of 3 checkers will have that square as the one that would make a parallelogram.  We'd have to figure a way to keep track of the multiple instances of disallowed squares.

I haven't worked it all out but my belief is that counting the squares this way will result in there being no more available open squares, but still some checkers to add.

Posted by Larry on 2005-07-13 02:38:42