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é

Soit \(n \geq 3\) un entier, et soit \(S_n\) l'ensemble des points \((x, y)\) du plan tels que \(x\) et \(y\) soient des entiers positifs ou nuls et que \(x + y < n\). Une droite du plan est dite intéressante si elle n'est parallèle ni à l'axe des abscisses, ni à l'axe des ordonnées, ni à la droite d'équation \(x + y = 0\).

Déterminer tous les entiers \(k\) positifs ou nuls pour lesquels il existe \(n\) droites vérifiant les deux conditions suivantes :

  • la réunion des \(n\) droites contient tous les points de \(S_n\) ;
  • exactement \(k\) de ces droites sont intéressantes.
Énoncé original (anglais)

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\)

Problèmes voisins

Sur les mêmes idées, à une difficulté proche :

  • 2021 C2 ★☆☆☆☆ : Quels nombres de billes ne peut-on pas placer en cercle avec toutes les couleurs dans chaque fenêtre de \(n + 1\) ?
  • 2013 C1 ★☆☆☆☆ : Des réels de \([0, 1]\) de somme \(n\) : combien de groupes de somme au plus \(1\) faut-il pour les répartir ?
  • 2020 G4 ★★☆☆☆ : \(n\) disques disjoints et un point \(O\) quelconque : la somme des distances de \(O\) à un point de chaque disque est au moins \(R_6 + \cdots + R_n\).
  • 2017 C4 ★★☆☆☆ · OIM P5 : Dans une rangée de \(N(N + 1)\) joueurs, on peut en garder \(2N\) où chaque paire de tailles consécutives est côte à côte.