Shortlist 2022, C7¶
Domaine : Combinatoire · Difficulté : ★★★★☆ · Proposé par : Czech Republic
Concepts : Invariants et monovariants · Principe des tiroirs
Solution officielle : Shortlist officielle 2022 (avec solutions), p. 36 (page 38 du PDF)
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
Lucy starts by writing \(s\) integer-valued \(2022\)-tuples on a blackboard. After doing that, she can take any two (not necessarily distinct) tuples \(\mathbf{v} = (v_1, \ldots, v_{2022})\) and \(\mathbf{w} = (w_1, \ldots, w_{2022})\) that she has already written, and apply one of the following operations to obtain a new tuple:
and then write this tuple on the blackboard.
It turns out that, in this way, Lucy can write any integer-valued \(2022\)-tuple on the blackboard after finitely many steps. What is the smallest possible number \(s\) of tuples that she initially wrote?
Indices : les idées clés
- Réponse : \(s = 3\) (et plus généralement \(s = 3\) pour des \(n\)-uplets avec \(n \geq 3\)).
- Construire une base : il suffit d'obtenir \(e^{(1)}, \ldots, e^{(n)}\) et \(c = (-1, \ldots, -1)\) ; on les tire de \(a_i = -i^2\), \(b_i = i\), \(c_i = -1\) grâce à \(1 - 2(i-j)^2\), qui vaut \(1\) en \(i = j\) et au plus \(-1\) ailleurs.
- Invariants et monovariants : une inégalité \(v_j \geq a v_k\) (\(a \geq 0\)), vraie pour les uplets de départ, est conservée par \(+\) et par \(\vee\) ; de même le signe d'une coordonnée.
- Principe des tiroirs : avec deux uplets de départ et au moins trois coordonnées, deux coordonnées ont la même configuration de signes.
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2022 (une solution, accompagnée de remarques communes).
Remarques communes du livret. (1) Pour \(n \in \{1, 2\}\), deux \(n\)-uplets de départ sont nécessaires et suffisants. (2) Les opérations \(+\) et \(\vee\) sont celles de la géométrie tropicale ; à la connaissance des auteurs, connaître la géométrie tropicale n'aide pas à résoudre le problème.
Réponse : le plus petit nombre possible est \(s = 3\).
Solution¶
On résout le problème pour des \(n\)-uplets avec \(n \geq 3\) quelconque : la réponse est \(s = 3\) quel que soit \(n\).
Notations. Pour un \(n\)-uplet \(v\), on note \(v_i\) sa \(i\)-ème coordonnée (\(1 \leq i \leq n\)). Pour un entier \(m \geq 1\), on note \(m \cdot v\) le uplet obtenu en additionnant \(v\) à lui-même \(m\) fois. On note \(e^{(i)}\) le uplet dont la \(i\)-ème coordonnée vaut \(1\) et toutes les autres \(0\).
Trois uplets suffisent. Soit \(c = (-1, \ldots, -1)\). Il suffit que Lucy puisse écrire \(e^{(1)}, \ldots, e^{(n)}\) et \(c\) : à partir d'eux, elle obtient tout uplet \(v\). En effet, on choisit un entier \(k \geq 1\) tel que \(k + v_i > 0\) pour tout \(i\) ; en additionnant un nombre positif de copies de \(c, e^{(1)}, \ldots, e^{(n)}\), elle peut écrire
qui est égal à \(v\) : sa \(i\)-ème coordonnée vaut \(-k + (k + v_i) = v_i\).
Lucy prend comme uplets de départ \(a\), \(b\) et \(c\), avec \(a_i = -i^2\), \(b_i = i\) et \(c = (-1, \ldots, -1)\).
Pour \(1 \leq j \leq n\), notons \(d^{(j)} = 2 \cdot a + 4j \cdot b + (2j^2 - 1) \cdot c\), que Lucy obtient par additions répétées de \(a\), \(b\) et \(c\). Sa \(i\)-ème coordonnée vaut
Elle vaut \(1\) si \(i = j\), et au plus \(-1\) sinon. Lucy peut donc écrire le uplet \(\mathbf{1} = (1, \ldots, 1)\) sous la forme \(d^{(1)} \vee \cdots \vee d^{(n)}\).
Elle écrit ensuite le uplet nul \(\mathbf{0} = \mathbf{1} + c\), puis, pour tout \(j\), \(e^{(j)} = d^{(j)} \vee \mathbf{0}\). Elle dispose alors de \(e^{(1)}, \ldots, e^{(n)}\) et de \(c\), donc (comme on l'a vu) de tout uplet à coordonnées entières.
Deux uplets ne suffisent pas. Observation. Soit \(a \geq 0\) un réel, et supposons que deux uplets \(v\) et \(w\) vérifient \(v_j \geq a v_k\) et \(w_j \geq a w_k\) pour certains \(1 \leq j, k \leq n\). Alors \(v + w\) et \(v \vee w\) vérifient la même inégalité. Pour la somme :
Pour l'autre opération, notons \(m = v \vee w\). Alors \(m_j \geq v_j \geq a v_k\) et \(m_j \geq w_j \geq a w_k\) ; comme \(m_k = v_k\) ou \(m_k = w_k\), on obtient \(m_j \geq a m_k\).
Par conséquent (invariant), si tous les uplets de départ vérifient une telle inégalité, tous les uplets obtenus la vérifient aussi, et Lucy ne peut pas écrire tous les uplets à coordonnées entières. (Précision ajoutée : avec \(j \neq k\), le uplet de coordonnées \(v_j = -1\), \(v_k = 1\) ne vérifie pas \(v_j \geq a v_k\).)
Supposons par l'absurde que Lucy parte de deux uplets \(v\) et \(w\) seulement. Premier cas : il existe une coordonnée \(i\) avec \(v_i, w_i \geq 0\). Les deux opérations conservent cette propriété, donc Lucy ne peut écrire aucun uplet dont la \(i\)-ème coordonnée est négative. De même si \(v_i, w_i \leq 0\).
Second cas : pour tout \(i\), on a soit \(v_i > 0 > w_i\), soit \(v_i < 0 < w_i\). Comme il y a au moins trois coordonnées et seulement deux configurations de signes possibles, par le principe des tiroirs, il existe deux coordonnées \(j \neq k\) telles que \(v_j\) a le même signe que \(v_k\) et \(w_j\) le même signe que \(w_k\).
Quitte à échanger \(v\) et \(w\), on suppose \(v_j, v_k > 0\) et \(w_j, w_k < 0\). Notons \(a = v_j / v_k > 0\). Si \(w_j / w_k \leq a\), alors les deux inégalités \(v_j \geq a v_k\) et \(w_j \geq a w_k\) sont vérifiées. Si au contraire \(w_j / w_k \geq a\) (le livret écrit de nouveau « \(\leq\) » ; il faut lire \(\geq\)), alors \(v_k \geq \frac{1}{a} v_j\) et \(w_k \geq \frac{1}{a} w_j\). Dans les deux cas, les deux uplets de départ vérifient une inégalité du type de l'observation, ce qui est une contradiction.
Donc \(s = 3\). \(\blacksquare\)