Aller au contenu

Shortlist 2017, C7

Domaine : Combinatoire · Difficulté : ★★★★☆ · Proposé par : U.S.A.

Concepts : Principe extrémal

Solution officielle : Shortlist officielle 2017 (avec solutions), p. 48 (page 50 du PDF)

Énoncé

Pour des ensembles finis \(X\) et \(Y\) d'entiers strictement positifs, on note \(f_X(k)\) le \(k\)-ième plus petit entier strictement positif qui n'appartient pas à \(X\), et l'on pose

\[X * Y = X \cup \{ f_X(y) : y \in Y \}.\]

Soit \(A\) un ensemble de \(a > 0\) entiers strictement positifs, et \(B\) un ensemble de \(b > 0\) entiers strictement positifs. Montrer que si \(A * B = B * A\), alors

\[\underbrace{A * (A * \cdots * (A * (A * A)) \ldots )}_{A \text{ apparaît } b \text{ fois}} = \underbrace{B * (B * \cdots * (B * (B * B)) \ldots )}_{B \text{ apparaît } a \text{ fois}}.\]
Énoncé original (anglais)

For any finite sets \(X\) and \(Y\) of positive integers, denote by \(f_X(k)\) the \(k\)-th smallest positive integer not in \(X\), and let

\[X * Y = X \cup \{ f_X(y) : y \in Y \}.\]

Let \(A\) be a set of \(a > 0\) positive integers, and let \(B\) be a set of \(b > 0\) positive integers. Prove that if \(A * B = B * A\), then

\[\underbrace{A * (A * \cdots * (A * (A * A)) \ldots )}_{A \text{ appears } b \text{ times}} = \underbrace{B * (B * \cdots * (B * (B * B)) \ldots )}_{B \text{ appears } a \text{ times}}.\]
Indices : les idées clés
  • Traduire \(*\) en composition de fonctions : \(f_{X*Y} = f_X \circ f_Y\), ce qui rend \(*\) associative et ramène le problème à des fonctions strictement croissantes.
  • Une fonction strictement croissante de \(\mathbb{Z}_{>0}\) dans lui-même est déterminée par son image : \(f_X = f_Y \iff X = Y\).
  • Principe extrémal : on considère le plus grand \(s\) appartenant à exactement un des deux ensembles (solution 1), ou le plus grand \(s\) tel que \(g^b(s) \neq h^a(s)\) (solution 2).
  • Comportement pour les grands entiers (solution 2) : \(f_A(n) = n + a\) dès que \(n \geq \max A\).
Solutions

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

Solution 1

Pour une fonction \(g : \mathbb{Z}_{>0} \to \mathbb{Z}_{>0}\) et une partie \(X \subset \mathbb{Z}_{>0}\), notons \(g(X) = \{g(x) : x \in X\}\). L'image de \(f_X\) est \(f_X(\mathbb{Z}_{>0}) = \mathbb{Z}_{>0} \setminus X\). Montrons d'abord un lemme général sur l'opération \(*\), dans le but de prouver qu'elle est associative.

Lemme 1. Pour toutes parties finies \(X\), \(Y\) de \(\mathbb{Z}_{>0}\), les fonctions \(f_{X*Y}\) et \(f_X \circ f_Y\) sont égales.

Preuve. On a

\[f_{X*Y}(\mathbb{Z}_{>0}) = \mathbb{Z}_{>0} \setminus (X*Y) = (\mathbb{Z}_{>0} \setminus X) \setminus f_X(Y) = f_X(\mathbb{Z}_{>0}) \setminus f_X(Y) = f_X(\mathbb{Z}_{>0} \setminus Y) = f_X(f_Y(\mathbb{Z}_{>0})),\]

l'avant-dernière égalité venant de l'injectivité de \(f_X\). Ainsi \(f_{X*Y}\) et \(f_X \circ f_Y\) sont deux fonctions strictement croissantes de même image. Comme une fonction strictement croissante est déterminée de façon unique par son image, \(f_{X*Y} = f_X \circ f_Y\). \(\square\)

Le lemme 1 entraîne que \(*\) est associative : \((A*B)*C = A*(B*C)\) pour toutes parties finies \(A\), \(B\), \(C\). En effet,

\[\mathbb{Z}_{>0} \setminus ((A*B)*C) = f_{(A*B)*C}(\mathbb{Z}_{>0}) = f_{A*B}(f_C(\mathbb{Z}_{>0})) = f_A(f_B(f_C(\mathbb{Z}_{>0})))\]
\[= f_A(f_{B*C}(\mathbb{Z}_{>0})) = f_{A*(B*C)}(\mathbb{Z}_{>0}) = \mathbb{Z}_{>0} \setminus (A*(B*C)).\]

On peut donc omettre les parenthèses, et on note

\[X^{*k} = \underbrace{X * (X * \cdots * (X * (X * X)) \ldots)}_{X \text{ apparaît } k \text{ fois}}.\]

Il s'agit de montrer que \(A*B = B*A\) entraîne \(A^{*b} = B^{*a}\). Nous utiliserons le lemme général suivant.

Lemme 2. Si \(X\) et \(Y\) sont des parties finies de \(\mathbb{Z}_{>0}\) telles que \(X*Y = Y*X\) et \(|X| = |Y|\), alors \(X = Y\).

Preuve. Supposons \(X \neq Y\). Par le principe extrémal, soit \(s\) le plus grand entier appartenant à exactement un des ensembles \(X\) et \(Y\) ; sans perte de généralité \(s \in X \setminus Y\). Le nombre \(f_X(s)\) est le \(s\)-ième entier hors de \(X\), donc

\[f_X(s) = s + \big|X \cap \{1, 2, \ldots, f_X(s)\}\big|. \tag{1}\]

Comme \(f_X(s) \geq s\), la maximalité de \(s\) donne

\[\{f_X(s)+1, f_X(s)+2, \ldots\} \cap X = \{f_X(s)+1, f_X(s)+2, \ldots\} \cap Y,\]

ce qui, avec \(|X| = |Y|\), donne

\[\big|X \cap \{1, 2, \ldots, f_X(s)\}\big| = \big|Y \cap \{1, 2, \ldots, f_X(s)\}\big|. \tag{2}\]

Considérons l'équation d'inconnue \(t\)

\[t - \big|Y \cap \{1, 2, \ldots, t\}\big| = s.\]

Elle n'est vérifiée que pour \(t \in [f_Y(s), f_Y(s+1))\), car le membre de gauche compte les entiers jusqu'à \(t\) qui ne sont pas dans \(Y\). D'après (1) et (2), \(t = f_X(s)\) la vérifie. De plus, comme \(f_X(s) \notin X\) et \(f_X(s) \geq s\) (en fait \(f_X(s) > s\) puisque \(s \in X\)), la maximalité de \(s\) donne \(f_X(s) \notin Y\). Le seul élément de \([f_Y(s), f_Y(s+1))\) hors de \(Y\) étant \(f_Y(s)\), on obtient \(f_X(s) = f_Y(s)\).

On aboutit alors à une contradiction. La valeur \(f_X(s)\) n'est ni dans \(X\), ni dans \(f_X(Y)\) (car \(s \notin Y\) et \(f_X\) est injective). Donc \(f_X(s) \notin X*Y\). Mais comme \(s \in X\), on a \(f_Y(s) \in Y*X\) : contradiction avec \(X*Y = Y*X\). \(\square\)

Concluons. D'abord, \(|X*Y| = |X| + |Y|\), donc \(|A^{*b}| = ab = |B^{*a}|\). Ensuite, comme \(A*B = B*A\) et que \(*\) est associative, on peut faire passer chaque \(A\) à travers chaque \(B\), d'où \(A^{*b} * B^{*a} = B^{*a} * A^{*b}\). Par le lemme 2, \(A^{*b} = B^{*a}\). \(\blacksquare\)

Solution 2

On utilise le lemme 1 de la solution 1, et la notation \(X^{*k}\). Si \(X\) et \(Y\) sont finies,

\[f_X = f_Y \iff f_X(\mathbb{Z}_{>0}) = f_Y(\mathbb{Z}_{>0}) \iff \mathbb{Z}_{>0} \setminus X = \mathbb{Z}_{>0} \setminus Y \iff X = Y, \tag{3}\]

la première équivalence venant de ce que \(f_X\) et \(f_Y\) sont strictement croissantes, la deuxième de \(f_X(\mathbb{Z}_{>0}) = \mathbb{Z}_{>0} \setminus X\).

Notons \(g = f_A\) et \(h = f_B\). D'après (3) et le lemme 1, la relation \(A*B = B*A\) équivaut à \(f_{A*B} = f_{B*A}\), c'est-à-dire à \(g \circ h = h \circ g\). De même, la relation voulue \(A^{*b} = B^{*a}\) équivaut à \(g^b = h^a\) (puissances au sens de la composition). Nous allons montrer que

\[g^b(n) = h^a(n) \tag{4}\]

pour tout \(n \in \mathbb{Z}_{>0}\), ce qui suffit.

D'abord, (4) est vraie pour tout \(n\) assez grand. En effet, soient \(p\) et \(q\) les plus grands éléments de \(A\) et \(B\) ; on peut supposer \(p \geq q\). Pour tout \(n \geq p\), on a \(g(n) = n + a\) et \(h(n) = n + b\), donc \(g^b(n) = n + ab = h^a(n)\).

Si (4) n'est pas toujours vraie, il existe donc, par le principe extrémal, un plus grand \(s\) tel que \(g^b(s) \neq h^a(s)\). Sans perte de généralité \(g(s) \neq s\) : sinon on aurait \(g(s) = h(s) = s\) (si \(g(s) = s\) et \(h(s) \neq s\), on échange les rôles), et \(s\) vérifierait (4). Comme \(g\) est croissante, \(g(s) \geq s\), donc \(g(s) > s\) et (4) est vraie pour \(n = g(s)\). Mais alors

\[g(g^b(s)) = g^{b+1}(s) = g^b(g(s)) = h^a(g(s)) = g(h^a(s)),\]

la dernière égalité venant de \(g \circ h = h \circ g\). Par injectivité de \(g\), on obtient \(g^b(s) = h^a(s)\), ce qui contredit le choix de \(s\). Ainsi (4) est vraie sur tout \(\mathbb{Z}_{>0}\). \(\blacksquare\)

Remarques

Remarque 1. En prenant \(A = X^{*k}\) et \(B = X^{*l}\), on obtient beaucoup d'exemples non triviaux avec \(A*B = B*A\). Il en existe d'autres, qui ne sont pas de cette forme : par exemple, pour \(A = \{1, 2, 4\}\) et \(B = \{1, 3\}\), on a \(A*B = \{1, 2, 3, 4, 6\} = B*A\).

Remarque 2 (autre preuve du lemme 2, esquisse). Soit \(n = |X| = |Y|\) ; soient \(u = \min X\) et \(v = \min Y\), avec sans perte de généralité \(u \leq v\). Pour une partie finie \(T\) de cardinal \(t\), écrivons \(X = \{x_1 < \cdots < x_n\}\) et posons \(S_m = f_{T * X^{*(m-1)}}(X)\), d'éléments \(s_{m,1} < \cdots < s_{m,n}\). Les \(S_m\) sont deux à deux disjoints : si \(m < m'\), alors \(S_m \subset T * X^{*m} \subset T * X^{*(m'-1)}\) et \(S_{m'} = (T * X^{*m'}) \setminus (T * X^{*(m'-1)})\).

Affirmation. Pour tout \(i\), il existe \(m_i\) et \(c_i\) tels que \(s_{m,i} = t + mn - c_i\) pour tout \(m > m_i\), et \(c_i\) ne dépend pas de \(T\). (Les \(S_m\) finissent par être des translatés les uns des autres.)

L'affirmation entraîne le lemme 2. On l'applique avec \(T = X\) puis \(T = Y\) (même cardinal \(t = n\)) : il existe \(m'\) tel que pour tout \(m \geq m'\),

\[f_{X^{*m}}(X) = f_{Y * X^{*(m-1)}}(X). \tag{5}\]

Comme \(u = \min X\), \(v = \min Y\) et \(u \leq v\), on a

\[\left( \bigcup_{m \geq m'} f_{X^{*m}}(X) \right) \cup X^{*m'} = \left( \bigcup_{m \geq m'} f_{Y * X^{*(m-1)}}(X) \right) \cup \left( Y * X^{*(m'-1)} \right) = \{u, u+1, \ldots\},\]

les deux réunions étant disjointes. Par (5), \(X^{*m'} = Y * X^{*(m'-1)}\). Comme \(X\) et \(Y\) commutent, \(X^{*(m'-1)} * X = X^{*(m'-1)} * Y\), et donc \(X = Y\) (par injectivité de \(f_{X^{*(m'-1)}}\)).

Preuve de l'affirmation. Récurrence descendante sur \(i\), en commençant par \(i = n\). Prenons \(m\) tel que tous les éléments de \(S_m\) dépassent ceux de \(T\). Pour \(i = n\), on a \(s_{m,n} > s_{k,n}\) pour tout \(k < m\) ; ainsi les \((m-1)n\) nombres \(s_{k,u}\) (\(k < m\), \(1 \leq u \leq n\)) sont inférieurs à \(s_{m,n}\), qui est donc le \(((m-1)n + x_n)\)-ième entier hors de \(T\), à savoir \(t + (m-1)n + x_n\). On peut donc prendre \(c_n = n - x_n\), qui ne dépend pas de \(T\). (Le livret écrit \(c_n = x_n - n\) ; avec la convention \(s_{m,i} = t + mn - c_i\), il faut lire \(c_n = n - x_n\).) Pour \(i < n\), tous les \(s_{m,j}\) avec \(j < i\) et les \(s_{p,i}\) avec \(p < m\) sont inférieurs à \(s_{m,i}\), donc \(s_{m,i}\) est le \(((m-1)i + x_i)\)-ième entier qui n'est ni dans \(T\), ni de la forme \(s_{p,j}\) avec \(j > i\) et \(p < m\). Par hypothèse de récurrence, chaque suite \((s_{p,j})_p\) est à terme de pas constant \(n\), donc \((s_{m,i})_m\) aussi ; et comme les \(s_{p,j} - t\) (\(j > i\)) ne dépendent finalement pas de \(T\), \(s_{m,i} - t\) non plus. \(\square\)

Problèmes voisins

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

  • 2024 C7 ★★★★☆ · OIM P3 : Chaque terme compte les apparitions du précédent : l'une des deux sous-suites de parité finit par être périodique.
  • 2023 A6 ★★★★☆ · OIM P3 : Trouver les suites d'entiers pour lesquelles \(P(a_n)\) est le produit des \(k\) termes suivants, pour un polynôme unitaire de degré \(k\).
  • 2021 G6 ★★★★☆ : Pour quels \(n\) tout \(n\)-gone convexe de côtés \(1\) contient-il un triangle équilatéral de côté \(1\) ?
  • 2015 C6 ★★★★☆ : Un ensemble d'entiers laisse une infinité d'entiers sans écriture unique comme somme d'un nombre impair de ses éléments.