Aller au contenu

Shortlist 2025, C1

Domaine : Combinatoire · Difficulté : ★☆☆☆☆ · Proposé par : U.S.A.

Concepts : Principe des tiroirs · Récurrence et constructions récursives · Géométrie combinatoire : enveloppe convexe, points du réseau

Solution officielle : Shortlist officielle 2025 (avec solutions), section C1 (livret PDF)

Problème 1 de l'OIM 2025

Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2025, où il était le problème 1 (jour 1).

Énoncé

Let \(n \geq 3\) be an integer, and let \(S_n\) be the set of points \((x, y)\) in the plane such that \(x\) and \(y\) are nonnegative integers and \(x + y < n\). A line in the plane is called interesting if it is not parallel to the \(x\)-axis, the \(y\)-axis, or the line \(x + y = 0\).

Determine all nonnegative integers \(k\) such that there exist \(n\) lines satisfying both of the following:

  • the union of the \(n\) lines contains every point of \(S_n\), and
  • exactly \(k\) of the lines are interesting.
Indices : les idées clés
Solutions

La solution ci-dessous suit la solution officielle de la Shortlist 2025 (une solution).

Réponse : pour tout \(n \geq 3\), les valeurs possibles sont \(k = 0\), \(k = 1\) et \(k = 3\).

Solution

Appelons ennuyeuse une droite qui n'est pas intéressante, et disons que le couple \((n, k)\) est bon s'il existe \(n\) droites, dont exactement \(k\) intéressantes, dont la réunion contient \(S_n\). Soit \(T\) le triangle délimité par les droites \(x = 0\), \(y = 0\) et \(x + y = n - 1\).

Lemme. Si \(n \geq 4\), \((n, k)\) est bon si et seulement si \((n - 1, k)\) est bon.

Preuve. Si \((n - 1, k)\) est bon, on prend \(n - 1\) droites couvrant \(S_{n-1}\), dont exactement \(k\) intéressantes, et on ajoute la droite ennuyeuse \(x + y = n - 1\) : ces \(n\) droites couvrent \(S_n\) et exactement \(k\) sont intéressantes.

Réciproquement, supposons \((n, k)\) bon avec \(n \geq 4\). Le bord de \(T\) contient \(3n - 3 > 2n\) points de \(S_n\). Si \(n\) droites couvrent \(S_n\), par le principe des tiroirs l'une d'elles, disons \(\ell\), rencontre le bord de \(T\) en au moins trois points. Alors \(\ell\) est un côté de \(T\), donc ennuyeuse. Les \(n - 1\) autres droites couvrent \(S_n\) privé des points de \(\ell\), et exactement \(k\) d'entre elles sont intéressantes. Or \(S_n\) privé des points de \(\ell\) est un translaté de \(S_{n-1}\), donc \((n - 1, k)\) est bon. \(\square\)

D'après le lemme (par récurrence), les valeurs possibles de \(k\) ne dépendent pas de \(n\) ; il suffit de traiter \(n = 3\). Les constructions pour \(k = 0, 1, 3\) sont les suivantes (en bleu, les droites intéressantes) :

Figure (solution)

  1. \(k = 0\) : les droites \(y = 0\), \(y = 1\) et \(y = 2\) ;
  2. \(k = 1\) : les droites \(y = 0\), \(y = 1\) et n'importe quelle droite intéressante passant par \((0, 2)\) (sur la figure, \(2x + y = 2\)) ;
  3. \(k = 3\) : les droites \(x = y\), \(2x + y = 2\) et \(x + 2y = 2\).

Pour \(k > 3\), il n'y a pas assez de droites (\(n = 3\)). Montrons enfin que \(k = 2\) est impossible pour \(n = 3\). Supposons que trois droites couvrent \(S_3\), dont exactement deux intéressantes.

Cas 1 : une des droites contient trois points de \(S_3\). C'est alors un côté de \(T\), donc une droite ennuyeuse. Les points de \(S_3\) qu'elle ne couvre pas forment un translaté de \(S_2\), qui doit être couvert par les deux droites intéressantes. C'est impossible, car toute droite passant par deux points de \(S_2\) est ennuyeuse.

Cas 2 : aucune droite ne contient trois points. Comme \(S_3\) a \(6\) points, chaque droite en contient exactement deux. Or il n'y a que trois droites intéressantes contenant exactement deux points de \(S_3\) : \(x = y\), \(2x + y = 2\) et \(x + 2y = 2\). On ne peut pas couvrir \(S_3\) avec deux d'entre elles et une droite ennuyeuse (les deux points restants sont toujours ceux de la troisième droite intéressante).

Donc \(k = 2\) est impossible, et la réponse est \(k \in \{0, 1, 3\}\). \(\blacksquare\)