Competition problem — Combinatorics

Combinatorics Difficulty 6.1 National Olympiad Prove it United States

Problem:

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.

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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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