Exercise 14. Consider a grid of size $2019 \times 2019$. On this grid, pebbles are placed. A configuration is said to be beautiful if there does not exist a parallelogram formed by four pebbles $A B C D$, such that $A, B, C$, and $D$ are not all aligned.

What is the maximum number of pebbles that can be placed on the grid?
Solution to Exercise 14 In this problem, we are looking for the largest integer satisfying a certain property. Suppose we want to show that the largest integer sought is the integer c. To show that c is indeed the largest integer, we will first show that if an integer n satisfies the property, then n ≤ c, and secondly, we will show that we can find a grid with exactly c pebbles satisfying the property.

We quickly test the statement for smaller values, for example, for a grid of size 3 × 3, 4 × 4, or even 5 × 5, in order to guess the value. In these small cases, the largest integers are 5, 7, and 9, respectively. We can conjecture that the value sought will therefore be 2 × 2019 - 1 = 4037. By testing these small values, we have noticed that the presence of pebbles in a column forces certain positions to be empty. We will therefore try to formalize this reasoning.

We consider pairs of pebbles that are in the same column. If there are two such pairs whose pebbles are at the same distance on different columns, then we obtain a parallelogram, which we want to avoid.

Let \( n_i \) be the number of pebbles in the i-th column. Consequently, there are at least \( n_i - 1 \) pairs with distinct distances on column i. Since for two fixed columns, the distance between any two pebbles in the first column must be different from the distance between any two pebbles in the second column, all the distances between pairs of pebbles in the same column must be distinct. This gives a total of \( (n_1 - 1) + (n_2 - 1) + \cdots + (n_{2019} - 1) = n - 2019 \) distinct distances with n being the total number of pebbles. Since there are at most 2018 possible distances, as there are 2019 positions for a pebble in a column, this shows that \( n \leq 2018 + 2019 = 4037 \).

Conversely, if we fill each cell in the first row with a pebble and each cell in the first column with a pebble and leave the other cells empty, we then place \( 2 \times 2019 - 1 = 4037 \) pebbles without creating any parallelograms.

The largest integer sought is therefore 4037.

Grader Comments

Many students had the right idea to solve the problem, but many had difficulty formalizing the result correctly. If one attempts to solve this problem by induction, it is necessary to explicitly state the grids being manipulated and to be careful that a sub-grid of a "maximal" grid is not necessarily maximal.