Track / Stage 6 / 108 of 400 #1588 of 2444

Problem 1588

National Olympiad, first round

Combinatorics Difficulty 6.1 Prove it BAMO-8 and BAMO-12 · United States

For $n > 1$ , consider an $n \times n$ chessboard and place pieces at the centers of different squares.

a. With $2n$ chess pieces on the board, show that there are 4 pieces among them that form the vertices of a parallelogram.

b. Show that there is a way to place $(2n-1)$ chess pieces so that no 4 of them form the vertices of a parallelogram.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Solution:

a. Since there can be at most $n$ pieces that are leftmost in their rows (some rows may be empty), there are at least $n$ pieces that are not the leftmost in their row. Record the distances (the number of squares) between the leftmost piece and the other pieces on the same row.

There are then at least $n$ distances recorded. Since the distances range from $1$ to $n-1$ , by the Pigeonhole Principle, at least two of these distances are the same. This implies that there are at least two rows each containing two pieces that are the same distance apart. These four pieces yield a parallelogram.

b. If $(2n-1)$ pieces are placed, for example, on the squares of the first column and the first row, then there is no parallelogram.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.