Solution: Four chess pieces

We publish here the solution to the four chess pieces divertimento.

The fun

A chessboard has size \(n \times n\), with \(n >1\). What is the smallest number of pieces to place on the board to ensure that four of them determine a parallelogram?

Solution

First of all we observe that there are four pieces forming a parallelogram if and only if there are two rows with two pieces at the same distance horizontally, as in the image of the statement.

The minimum number of pieces is \(2n\). Indeed, \(2n -1\) pieces can be placed along a row and a column, which do not generate a parallelogram. Let us see that with \(2n\) pieces a parallelogram is guaranteed to exist.

Let \(F_1, \ldots, F_m\), with \(2\leq m\leq n\), be the rows containing at least \(2\) pieces, and let \(d_1, \ldots, d_k\) denote the distances from the leftmost pieces in each row to each of the pieces to their right. Because of the size of the board, \(1 \leq d_i \leq n-1\) for \(i=1,\ldots,k\).

There are \(n-m\) rows that have at most one piece. Therefore, the total number of pieces in the rows \(F_1, \ldots , F_m\) is greater than or equal to \(2n-(n-m) = n+m\). Among those pieces, \(m\) of them are the leftmost piece of their row. Therefore, we can deduce that \(k\), the number of distances \(d_1, \ldots, d_k\), is at least \((n+m)-m =n\).

By the pigeonhole principle, there must be two equal distances, which must necessarily come from different rows, and therefore generate a parallelogram.