Shortlist 2017, C4¶
Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : Russia
Concepts : Principe des tiroirs · Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2017 (avec solutions), p. 42 (page 44 du PDF)
Problème 5 de l'OIM 2017
Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2017, où il était le problème 5 (jour 2).
Énoncé¶
Let \(N \geq 2\) be an integer. \(N(N+1)\) soccer players, no two of the same height, stand in a row in some order. Coach Ralph wants to remove \(N(N-1)\) people from this row so that in the remaining row of \(2N\) players, no one stands between the two tallest ones, no one stands between the third and the fourth tallest ones, \(\ldots\), and finally no one stands between the two shortest ones. Show that this is always possible.
Indices : les idées clés
- Découper la rangée en \(N\) blocs de \(N+1\) personnes consécutives (solutions 1 et 3) : deux personnes d'un même bloc ne peuvent être séparées que par des membres de ce bloc.
- Principe des tiroirs (solution 2) : parmi les \(N+1\) premières personnes de la rangée, deux appartiennent au même des \(N\) groupes de taille.
- Récurrence et constructions récursives : on choisit une paire, on élimine son groupe et on recommence avec \(N-1\) groupes d'au moins \(N\) personnes.
- Dualité positions/tailles (remarque 1) : les solutions 1 et 2 se déduisent l'une de l'autre en échangeant les rôles de la position et de la taille.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2017 (trois solutions et deux remarques).
Solution 1¶
Découpons la rangée en \(N\) blocs de \(N+1\) personnes consécutives. Nous allons montrer comment retirer \(N-1\) personnes de chaque bloc pour satisfaire le souhait de l'entraîneur.
Construisons d'abord une matrice \((N+1) \times N\) dont le coefficient \(x_{i,j}\) est la taille de la \(i\)-ième personne la plus grande du \(j\)-ième bloc : chaque colonne liste les tailles d'un bloc, rangées par ordre décroissant de haut en bas.
Réordonnons cette matrice en permutant des colonnes entières. D'abord, par une permutation des colonnes, on fait en sorte que \(x_{2,1} = \max\{x_{2,i} : i = 1, 2, \ldots, N\}\) (la première colonne contient la plus grande valeur de la deuxième ligne). La première colonne étant fixée, on permute les autres pour que \(x_{3,2} = \max\{x_{3,i} : i = 2, \ldots, N\}\) (la deuxième colonne contient la plus grande valeur de la troisième ligne, première colonne exclue). En général, à l'étape \(k\) (\(k = 1, 2, \ldots, N-1\)), on permute les colonnes \(k\) à \(N\) de sorte que
Comme chaque colonne est décroissante, on obtient alors
En effet \(x_{k,k-1} > x_{k,k}\) par le choix de la colonne \(k-1\), et \(x_{k,k} > x_{k+1,k}\) car la colonne \(k\) est décroissante.
Le choix décisif. Dans la rangée initiale, on retire tout le monde sauf les \(2N\) personnes de tailles figurant dans \((*)\).
Bien sûr, l'ordre des tailles \((*)\) n'est pas forcément l'ordre des positions dans la nouvelle rangée. D'après \((*)\), les deux plus grands sont \(x_{1,1}, x_{2,1}\), les troisième et quatrième sont \(x_{2,2}, x_{3,2}\), etc. : les paires à vérifier sont les \((x_{k,k}, x_{k+1,k})\). Il faut donc s'assurer que chaque paire \((x_{k,k}, x_{k+1,k})\) reste côte à côte dans la nouvelle rangée. Or \(x_{k,k}\) et \(x_{k+1,k}\) appartiennent à la même colonne, c'est-à-dire au même bloc de \(N+1\) personnes consécutives : les seules personnes qui pourraient se trouver entre elles étaient aussi dans ce bloc, et elles ont toutes été retirées. \(\blacksquare\)
Solution 2¶
Répartissons les joueurs en \(N\) groupes selon leur taille : \(G_1\) contient les \(N+1\) plus grands, \(G_2\) les \(N+1\) suivants, etc., jusqu'à \(G_N\) qui contient les \(N+1\) plus petits.
Parcourons la rangée initiale de gauche à droite, en nous arrêtant dès que nous avons parcouru deux personnes (consécutives ou non) d'un même groupe, disons \(G_i\). Comme il y a \(N\) groupes, par le principe des tiroirs cela arrive au plus tard à la \((N+1)\)-ième personne de la rangée. On choisit cette paire, et on retire toutes les autres personnes du groupe \(G_i\) ainsi que toutes les personnes déjà parcourues. Les seules personnes qui pourraient séparer les tailles de cette paire étaient dans \(G_i\) (elles sont parties) ; les seules qui pourraient séparer leurs positions avaient déjà été parcourues (elles sont parties aussi).
Il reste \(N-1\) groupes (tous sauf \(G_i\)). Chacun a perdu au plus une personne (sinon on se serait arrêté plus tôt), donc chacun a encore au moins \(N\) personnes non parcourues dans la rangée. On recommence le parcours de gauche à droite à partir de là, on choisit les deux prochaines personnes d'un même groupe, on retire ce groupe et tous ceux qui ont été parcourus. On obtient de nouveau deux personnes voisines dans la rangée restante, dont les tailles ne peuvent être séparées par personne d'autre (le reste de leur groupe est parti). Après ces 2 paires, il reste \(N-2\) groupes d'au moins \(N-1\) personnes chacun.
En répétant le parcours \(N\) fois au total, on garde exactement 2 personnes de chaque groupe, soit \(2N\) personnes. L'ordre des tailles est garanti par le découpage en groupes, et la construction de gauche à droite garantit que les deux personnes d'un même groupe sont côte à côte dans la rangée finale. \(\blacksquare\)
Solution 3¶
C'est essentiellement la solution 1 présentée par récurrence. Le cœur de l'argument est le lemme suivant.
Lemme. Soient \(N\) groupes disjoints d'au moins \(N+1\) personnes chacun, toutes de tailles distinctes. On peut choisir deux personnes dans chaque groupe de sorte que, parmi les personnes choisies, les deux plus grandes soient dans un même groupe, la troisième et la quatrième aussi, \(\ldots\), et les deux plus petites aussi.
Preuve. Récurrence sur \(N \geq 1\) ; pour \(N = 1\) c'est évident.
Soient \(N \geq 2\) et des groupes \(G_1, \ldots, G_N\) d'au moins \(N+1\) personnes. Numérotons les personnes \(1, 2, \ldots\) selon leur taille, de la plus grande à la plus petite. Soit \(s\) le plus petit entier tel que deux personnes parmi \(1, 2, \ldots, s\) soient dans un même groupe (sans perte de généralité \(G_N\)). Par minimalité de \(s\), ces deux personnes de \(G_N\) sont \(s\) et un certain \(i < s\).
On choisit les personnes \(i\) et \(s\) de \(G_N\), on oublie ce groupe, et on retire les personnes \(1, 2, \ldots, s\) de \(G_1, \ldots, G_{N-1}\). Encore par minimalité de \(s\), chaque groupe a perdu au plus une personne, donc les groupes obtenus \(G'_1, \ldots, G'_{N-1}\) contiennent chacun au moins \(N\) personnes. Par hypothèse de récurrence, on peut choisir une paire dans chacun de \(G'_1, \ldots, G'_{N-1}\) en respectant les conditions. Comme toutes ces personnes ont des numéros supérieurs à \(s\), l'ajout de la paire \((i, s)\) de \(G_N\) (qui sont les deux plus grandes personnes choisies) ne viole pas les conditions. \(\square\)
Pour résoudre le problème, il suffit de découper la rangée en \(N\) groupes contigus de \(N+1\) personnes et d'appliquer le lemme à ces groupes : deux personnes choisies dans un même groupe contigu ne peuvent être séparées que par des membres de ce groupe, qui ne sont pas choisis. \(\blacksquare\)
Remarques¶
Remarque 1 (dualité). On peut identifier chaque personne à un couple d'indices \((p, h)\), \(p, h \in \{1, 2, \ldots, N(N+1)\}\), de sorte que la \(p\)-ième personne de la rangée (de gauche à droite) soit la \(h\)-ième plus grande. Disons que \((a, b)\) sépare \((x_1, y_1)\) et \((x_2, y_2)\) si \(a\) est strictement entre \(x_1\) et \(x_2\), ou \(b\) est strictement entre \(y_1\) et \(y_2\). (Le livret écrit « \(a\) entre \(x_1\) et \(y_1\), ou \(b\) entre \(x_2\) et \(y_2\) » ; il faut lire comme ci-dessus.) L'entraîneur veut choisir \(2N\) personnes \((p_i, h_i)\), \(i = 1, \ldots, 2N\), telles qu'aucune personne choisie ne sépare \((p_1, h_1)\) de \((p_2, h_2)\), aucune ne sépare \((p_3, h_3)\) de \((p_4, h_4)\), etc. Cette formulation révèle une dualité entre positions et tailles ; en ce sens, les solutions 1 et 2 sont duales l'une de l'autre.
Remarque 2 (optimalité). Le nombre \(N(N+1)\) est optimal pour \(N = 2\) et \(N = 3\), comme le montrent les rangées (tailles de gauche à droite) \(1, 5, 3, 4, 2\) et \(1, 10, 6, 4, 3, 9, 5, 8, 7, 2, 11\).