Shortlist 2020, C3¶

Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : India

Solution officielle : Shortlist officielle 2020 (avec solutions), p. 33 (page 35 du PDF)

Problème 4 de l'OIM 2020

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

Énoncé¶

Let \(n\) be an integer with \(n \geq 2\). On a slope of a mountain, \(n^2\) checkpoints are marked, numbered from \(1\) to \(n^2\) from the bottom to the top. Each of two cable car companies, \(A\) and \(B\), operates \(k\) cable cars numbered from \(1\) to \(k\); each cable car provides a transfer from some checkpoint to a higher one. For each company, and for any \(i\) and \(j\) with \(1 \leq i < j \leq k\), the starting point of car \(j\) is higher than the starting point of car \(i\); similarly, the finishing point of car \(j\) is higher than the finishing point of car \(i\). Say that two checkpoints are linked by some company if one can start from the lower checkpoint and reach the higher one by using one or more cars of that company (no movement on foot is allowed).

Determine the smallest \(k\) for which one can guarantee that there are two checkpoints that are linked by each of the two companies.

Indices : les idées clés

Construction pour la borne : avec \(n^2 - n\) téléphériques, la compagnie \(A\) relie les points d'un même bloc de \(n\) points consécutifs, la compagnie \(B\) les points de même reste modulo \(n\).
Décomposition en chaînes : chaque point de contrôle appartient à une unique \(A\)-chaîne et à une unique \(B\)-chaîne ; le nombre de chaînes est égal au nombre de points qui ne sont pas l'arrivée d'un téléphérique, soit \(n^2 - k\).
Principe des tiroirs : \(n^2\) points pour seulement \((n-1)^2\) couples (\(A\)-chaîne, \(B\)-chaîne).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2020 (une solution et deux remarques).

Réponse : \(k = n^2 - n + 1\).

Solution¶

Pour \(k \leq n^2 - n\), il peut n'exister aucun couple de points reliés par les deux compagnies. Il suffit de donner un exemple pour \(k = n^2 - n\) (pour \(k\) plus petit, on ne garde qu'une partie des téléphériques, ce qui ne crée pas de nouvelles liaisons).

Que la compagnie \(A\) relie les couples de points \((i, i+1)\) avec \(n \nmid i\) : il y a bien \(n^2 - 1 - (n - 1) = n^2 - n\) téléphériques. Tout couple \((i, j)\) relié par \(A\) vérifie alors \(\lceil i/n \rceil = \lceil j/n \rceil\). Que la compagnie \(B\) relie les couples \((i, i+n)\) avec \(1 \leq i \leq n^2 - n\). Tout couple \((i, j)\) relié par \(B\) vérifie \(i \equiv j \pmod{n}\). Clairement, aucun couple \((i, j)\) avec \(i < j\) ne vérifie les deux conditions, donc aucun couple n'est relié par les deux compagnies.

Pour \(k = n^2 - n + 1\), il existe toujours deux points reliés par les deux compagnies. Appelons \(A\)-chaîne une suite de points \(a_1 < a_2 < \cdots < a_t\) telle que la compagnie \(A\) relie (par un téléphérique) \(a_i\) à \(a_{i+1}\) pour tout \(1 \leq i \leq t - 1\), mais qu'aucun téléphérique de \(A\) n'arrive en \(a_1\) ni ne parte de \(a_t\). On définit de même les \(B\)-chaînes. En avançant puis en reculant (de chaque point part au plus un téléphérique de \(A\) et à chaque point en arrive au plus un), on voit que tout point appartient à une unique \(A\)-chaîne (éventuellement réduite à ce point) et à une unique \(B\)-chaîne. Associons à chaque point le couple formé de sa \(A\)-chaîne et de sa \(B\)-chaîne.

Les points d'arrivée des téléphériques de \(A\) sont deux à deux distincts, donc exactement \(n^2 - k = n - 1\) points ne sont pas des points d'arrivée. Chacun d'eux est le point de départ d'une unique \(A\)-chaîne, et réciproquement, donc il y a \(n - 1\) \(A\)-chaînes. De même, il y a \(n - 1\) \(B\)-chaînes. Il y a donc \((n-1)^2\) couples (\(A\)-chaîne, \(B\)-chaîne). Comme \(n^2 > (n-1)^2\), d'après le principe des tiroirs, deux des \(n^2\) points correspondent au même couple : ils appartiennent à la même \(A\)-chaîne et à la même \(B\)-chaîne, donc ils sont reliés par les deux compagnies. \(\blacksquare\)

Remarques¶

Remarque 1. La condition selon laquelle le \(i\)-ème téléphérique part et arrive plus bas que le \(j\)-ème n'est utilisée que dans l'argument « en avançant puis en reculant » et dans le décompte des points de départ des chaînes. Dans les deux cas, l'hypothèse plus faible suivante suffit : deux téléphériques d'une même compagnie ne partent jamais du même point et n'arrivent jamais au même point. On pourrait donc affaiblir ainsi l'énoncé sans changer la solution.

Remarque 2. Avec \(N\) points de contrôle au lieu de \(n^2\), la réponse serait \(N - \lceil \sqrt{N} \rceil + 1\) ; la solution ci-dessus s'applique mot pour mot à cette généralisation.