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 20050713 02:38:42 