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.
In each non-empty row, the difference in squares between 2 checkers, let's call it the
gap, is anywhere between 1 to 7.
In a non-empty row with
k checkers, the number of different
gaps is at most (
k - 1). If the row is empty, then the number of different gaps is 0.
In otherwords, in a row with
k checkers, the number of different
gaps is either
k or
k - 1.
We assume that we cannot choose some four checkers. Clearly, this means that every
gap is distinct. This is because if two
gaps from different rows are the same, we are done.
If all the
gaps are distinct,
then summing up all the gaps over all 8 rows, we have anywhere from 16
- 8 = 8 to 16 - 2 = 14 distinct gaps. (8 is for the case where each row
has 2 counters, 14 when 2 rows have all counters). But since 14 > 8
> 7, clearly we have 2
gaps that are the same by Pigeonhole Principle. Thus we can find the 4 counters.
I think this is a solution...
