Question

WITH SOLUTION PLEASE

For n > 1; let 2n chess pieces be placed at the centers of 2n squares of
an n n chessboard. Show that there are four pieces among them that
formed the vertices of a parallelogram. If 2n is replaced by 2n-1; is the statement still true in general?

Answer 1

Let m be the number of rows that have at least 2 pieces. (Then each of the remaining n - m rows contains at most 1 piece.) For each of these m rows, locate the leftmost square that contains a piece. Record the distances (i.e. number of squares) between this piece and the other pieces on the same row. The distances can only be 1; 2.............;n - 1 because there are n columns.

Since the number of pieces in these m rows altogether is at least 2n - (n -m) = n + m; there are at least (n + m) - m = n distances recorded altogether for these m rows. By the pigeonhole principle, at least two of these distances are the same. This implies there are at least two rows each containing 2 pieces that are of the same distance apart. These 4 pieces yield a parallelogram.

 For the second question, placing 2n - 1 pieces on the squares of the first row and first column shows there are no parallelograms.