Shortlist 2017, C7¶

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

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

Pas encore relu

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

Énoncé¶

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\)