Aller au contenu

Shortlist 2021, C8

Domaine : Combinatoire · Difficulté : ★★★★★ · Proposé par : non indiqué

Concepts : Principe des tiroirs · Récurrence et constructions récursives

Solution officielle : Shortlist officielle 2021 (avec solutions), p. 39 (page 39 du PDF)

Pas encore relu

Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.

Énoncé

Determine the largest \(N\) for which there exists a table \(T\) of integers with \(N\) rows and \(100\) columns that has the following properties:

(i) Every row contains the numbers \(1, 2, \ldots, 100\) in some order.

(ii) For any two distinct rows \(r\) and \(s\), there is a column \(c\) such that \(|T(r, c) - T(s, c)| \geq 2\).

Here \(T(r, c)\) means the number at the intersection of the row \(r\) and the column \(c\).

Indices : les idées clés
  • Motifs : en remplaçant \(2k-1\) et \(2k\) par un même symbole \(x_k\), deux lignes de même motif violent (ii) ; il y a \(100!/2^{50}\) motifs.
  • Principe des tiroirs : deux lignes distinctes ont des motifs distincts, donc \(N \leq 100!/2^{50}\).
  • Récurrence et constructions récursives : on traduit chaque motif en ligne en plaçant \(2k-1\) et \(2k\) à l'étape \(k\), de sorte que \(2k-2, 2k-1, 2k\) apparaissent dans un ordre « cyclique ».
  • Plus grand symbole non aligné (solution 1) : on compare deux lignes à partir du plus grand \(k\) tel que \(x_k\) n'occupe pas les mêmes colonnes.
  • Parité des sous-permutations (solution 2) : deux lignes « voisines » diffèrent par des transpositions disjointes \((j, j+1)\), ce qui change la parité d'une des sous-permutations imposées.
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2021 (deux solutions et deux remarques ; la solution 2 redémontre autrement que l'exemple de la solution 1 convient).

Réponse : le plus grand \(N\) est \(N = \dfrac{100!}{2^{50}}\).

Solution 1

Il ne peut pas y avoir plus de lignes. Fixons une ligne du tableau et remplaçons, pour \(k = 1, 2, \ldots, 50\), chacun des deux nombres \(2k-1\) et \(2k\) par le symbole \(x_k\). On obtient un motif : une disposition des \(50\) symboles \(x_1, \ldots, x_{50}\), chacun apparaissant exactement deux fois. Il y a exactement \(N = \frac{100!}{2^{50}}\) motifs distincts \(P_1, \ldots, P_N\).

Si deux lignes \(r \neq s\) ont le même motif, alors \(|T(r, c) - T(s, c)| \leq 1\) pour toute colonne \(c\), ce qui contredit (ii). Par le principe des tiroirs, des lignes différentes ont des motifs différents, donc il y a au plus \(\frac{100!}{2^{50}}\) lignes.

Construction d'un tableau à \(N\) lignes. On traduit chaque motif \(P_i\) en une ligne contenant \(1, 2, \ldots, 100\) par une construction récursive : aux étapes \(k = 1, 2, \ldots, 50\) (dans cet ordre), on remplace les deux occurrences de \(x_k\) par \(2k-1\) et \(2k\).

  • L'occurrence de gauche de \(x_1\) devient \(1\), celle de droite devient \(2\).

  • Pour \(k \geq 2\), le nombre \(2k-2\) est déjà placé, et on place \(2k-1\) et \(2k\) de sorte que les trois nombres \(2k-2\), \(2k-1\), \(2k\) apparaissent (de gauche à droite) dans l'un des ordres

    \[(2k-2,\ 2k-1,\ 2k), \qquad (2k,\ 2k-2,\ 2k-1), \qquad (2k-1,\ 2k,\ 2k-2).\]

    C'est possible (et d'une seule façon), car \(2k-2\) se trouve avant, entre ou après les deux occurrences de \(x_k\).

Vérification de (ii). Considérons deux lignes \(r \neq s\), issues des motifs \(P_r\) et \(P_s\). Disons qu'un symbole \(x_i\) est aligné s'il occupe les mêmes deux colonnes dans \(P_r\) et dans \(P_s\). Soit \(k\) le plus grand indice tel que \(x_k\) ne soit pas aligné ; on a \(k \geq 2\) (si \(x_2, \ldots, x_{50}\) étaient alignés, \(x_1\) le serait aussi et les motifs seraient égaux).

Soit \(c_1\) la colonne où \(T(r, c_1) = 2k\) et \(c_2\) celle où \(T(s, c_2) = 2k\). Comme tous les \(x_i\) avec \(i \geq k+1\) sont alignés, les nombres supérieurs à \(2k\) occupent les mêmes colonnes dans les deux lignes, donc \(T(r, c_2) \leq 2k\) et \(T(s, c_1) \leq 2k\).

  • Si \(T(r, c_2) \leq 2k-2\), alors \(|T(r, c_2) - T(s, c_2)| \geq 2\), comme voulu.
  • Si \(T(s, c_1) \leq 2k-2\), alors \(|T(r, c_1) - T(s, c_1)| \geq 2\), comme voulu.
  • Si \(T(r, c_2) = 2k-1\) et \(T(s, c_1) = 2k-1\), alors \(x_k\) occupe les colonnes \(c_1, c_2\) dans les deux lignes, donc il est aligné : contradiction.

Dans le seul cas restant, \(c_1 = c_2\), c'est-à-dire \(T(r, c_1) = T(s, c_1) = 2k\). Considérons alors les colonnes \(d_1\) et \(d_2\) telles que \(T(r, d_1) = 2k-1\) et \(T(s, d_2) = 2k-1\). On a \(d_1 \neq d_2\) (car \(x_k\) n'est pas aligné), et \(T(r, d_2) \leq 2k-2\), \(T(s, d_1) \leq 2k-2\) (car les \(x_i\) avec \(i \geq k+1\) sont alignés).

  • Si \(T(r, d_2) \leq 2k-3\), alors \(|T(r, d_2) - T(s, d_2)| \geq 2\), comme voulu.
  • Si \(T(s, d_1) \leq 2k-3\), alors \(|T(r, d_1) - T(s, d_1)| \geq 2\), comme voulu. (Le livret écrit ici \(T(s, c_1)\) ; il faut lire \(T(s, d_1)\).)

Dans le seul cas restant, \(T(r, d_2) = 2k-2\) et \(T(s, d_1) = 2k-2\). Alors la ligne \(r\) contient \(2k-2, 2k-1, 2k\) dans les colonnes \(d_2, d_1, c_1\), et la ligne \(s\) les contient dans les colonnes \(d_1, d_2, c_1\). Ces deux dispositions diffèrent par l'échange de deux nombres, donc elles ne peuvent pas toutes deux être l'un des trois ordres autorisés (qui se déduisent les uns des autres par permutation circulaire) : c'est la contradiction finale. \(\blacksquare\)

Solution 2

On donne une autre preuve que l'exemple de la solution 1 (voir aussi la remarque 1) convient.

Lemme. Soient \(\pi_1\) et \(\pi_2\) deux permutations de \(\{1, 2, \ldots, n\}\) telles que \(|\pi_1(i) - \pi_2(i)| \leq 1\) pour tout \(i\). Alors il existe un ensemble de paires disjointes \((i, i+1)\) tel que \(\pi_2\) s'obtienne à partir de \(\pi_1\) en échangeant les éléments de chacune de ces paires.

Preuve. On peut supposer \(\pi_1(i) = i\) pour tout \(i\), et on raisonne par récurrence sur \(n\). Le cas \(n = 1\) est trivial. Si \(\pi_2(n) = n\), on applique l'hypothèse de récurrence. Si \(\pi_2(n) = n-1\), alors \(\pi_2(i) = n\) pour un certain \(i < n\) ; nécessairement \(i = n-1\) (car \(|n - i| \leq 1\)), et on applique encore l'hypothèse de récurrence. \(\square\)

Soient maintenant \(\pi_1\) et \(\pi_2\) deux lignes distinctes du tableau construit dans la solution 1 (vues comme des permutations de \(\{1, \ldots, 100\}\)), et supposons \(|\pi_1(i) - \pi_2(i)| \leq 1\) pour tout \(i\). D'après le lemme, il existe un ensemble non vide \(S \subset \{1, \ldots, 99\}\), dont deux éléments quelconques diffèrent d'au moins \(2\), tel que \(\pi_2\) s'obtienne à partir de \(\pi_1\) en appliquant les transpositions \((j, j+1)\), \(j \in S\). Soit \(r = \min S\).

  • Si \(r = 2k-1\) est impair, alors \(\pi_1\) et \(\pi_2\) induisent sur \(\{2k-2, 2k-1, 2k\}\) (ou sur \(\{1, 2\}\) si \(k = 1\)) des sous-permutations de parités opposées : impossible.
  • Donc \(r = 2k\) est pair. Comme \(\pi_1\) et \(\pi_2\) induisent des sous-permutations de même parité (paire) sur \(\{2k, 2k+1, 2k+2\}\), on doit avoir \(2k+2 \in S\). Puis \(2k+4 \in S\), et ainsi de suite jusqu'à \(98 \in S\). Mais alors les sous-permutations de \(\{98, 99, 100\}\) induites par \(\pi_1\) et \(\pi_2\) sont de parités opposées.

C'est une contradiction, donc deux lignes distinctes vérifient (ii). \(\blacksquare\)

Remarques

Remarque 1. On peut identifier les lignes de \(T\) à des permutations de \(M = \{1, \ldots, 100\}\) ; pour tout \(S \subset M\), chaque ligne induit une sous-permutation de \(S\) (en ignorant les nombres hors de \(S\)). L'exemple de la solution 1 est formé de toutes les permutations dont les sous-permutations induites sur les \(50\) ensembles \(\{1, 2\}, \{2, 3, 4\}, \{4, 5, 6\}, \ldots, \{98, 99, 100\}\) sont paires.

Remarque 2. La solution 2 utilise seulement le fait que, pour chacun des ensembles \(\{1, 2\}, \{2, 3, 4\}, \ldots, \{98, 99, 100\}\), deux lignes quelconques de \(T\) induisent des sous-permutations de même parité, pas forcément paire.