Problem 1399

Solution:

Dans ce problème, on cherche le plus grand entier satisfaisant une certaine propriété. Supposons que l'on veuille montrer que le plus grand entier recherché est l'entier $c$. Pour montrer que $c$ est bien le plus grand entier, on va d'une part montrer que si un entier $n$ satisfait la propriété, alors $n \leqslant c$ et d'autre part on va montrer que l'on peut trouver une grille possédant exactement $c$ cailloux satisfaisant la propriété.

On s'empresse de tester l'énoncé pour des valeurs plus petites, par exemple pour une grille de taille $3 \times 3$, $4 \times 4$ ou même $5 \times 5$, afin de deviner la valeur. On trouve dans ces petits cas que les plus grands entiers sont respectivement $5$, $7$ et $9$. On peut conjecturer que la valeur recherchée sera donc $2 \times 2019 - 1 = 4037$. En testant ces petites valeurs, on a pu remarquer que la présence de cailloux sur une colonne forçait que certains emplacements soient vides. Nous allons donc essayer de formaliser ce raisonnement.

On considère les paires de cailloux qui sont sur la même colonne. S'il y a deux telles paires dont les cailloux sont à même distance sur des colonnes différentes alors on obtient un parallélogramme, ce que l'on veut éviter.

Soit $n_{i}$ le nombre de cailloux dans la $i$-ième colonne. Sur la colonne $i$ il y a par conséquent au moins $n_{i}-1$ paires à distances distinctes. Puisque pour deux colonnes fixées, la distance entre deux quelconques cailloux de la première colonne doit être différente de la distance entre deux quelconques cailloux de la deuxième colonne, toutes les distances entre deux paires de cailloux appartenant à la même colonne doivent être distinctes. Cela fait en tout $\left(n_{1}-1\right)+\left(n_{2}-1\right)+\cdots+\left(n_{2019}-1\right)=n-2019$ distances distinctes avec $n$ le nombre total de cailloux. Or il y a au plus $2018$ distances possibles, puisqu'il y a $2019$ emplacements pour un caillou dans une colonne. Ceci montre que $n \leqslant 2018+2019=4037$.

Réciproquement, si on remplit chaque case de la première ligne par un caillou et chaque case de la première colonne par un caillou et on laisse les autres cases vides, on a alors placé $2 \times 2019-1=4037$ cailloux sans créer de parallélogrammes.

Le plus grand entier recherché est donc $4037$.