Shortlist 2019, C9¶
Domaine : Combinatoire · Difficulté : ★★★★★ · Proposé par : Italy
Concepts : Récurrence et constructions récursives · Principe extrémal
Solution officielle : Shortlist officielle 2019 (avec solutions), section C9 (livret PDF)
Énoncé¶
Pour deux nombres réels distincts \(x\) et \(y\), on définit \(D(x, y)\) comme l'unique entier \(d\) vérifiant \(2^d \leq |x - y| < 2^{d+1}\). Étant donnés un ensemble de réels \(\mathcal{F}\) et un élément \(x \in \mathcal{F}\), on appelle échelles de \(x\) dans \(\mathcal{F}\) les valeurs de \(D(x, y)\) pour \(y \in \mathcal{F}\) avec \(x \neq y\).
Soit \(k\) un entier strictement positif donné. On suppose que chaque élément \(x\) de \(\mathcal{F}\) a au plus \(k\) échelles différentes dans \(\mathcal{F}\) (ces échelles pouvant dépendre de \(x\)). Quel est le cardinal maximal possible de \(\mathcal{F}\) ?
Énoncé original (anglais)
For any two different real numbers \(x\) and \(y\), we define \(D(x, y)\) to be the unique integer \(d\) satisfying \(2^d \leq |x - y| < 2^{d+1}\). Given a set of reals \(\mathcal{F}\), and an element \(x \in \mathcal{F}\), we say that the scales of \(x\) in \(\mathcal{F}\) are the values of \(D(x, y)\) for \(y \in \mathcal{F}\) with \(x \neq y\).
Let \(k\) be a given positive integer. Suppose that each member \(x\) of \(\mathcal{F}\) has at most \(k\) different scales in \(\mathcal{F}\) (note that these scales may depend on \(x\)). What is the maximum possible size of \(\mathcal{F}\)?
Indices : les idées clés
- Pondération : on attribue à chaque \(x \in S\) le poids \(2^{-r_S(x)}\), où \(r_S(x)\) est le nombre d'échelles de \(x\) dans \(S\), et on montre que le poids total est au plus \(1\).
- Récurrence sur \(|S|\) : on coupe \(S\) en deux sous-ensembles plus petits \(S_O\) et \(S_E\) dont les poids encadrent celui de \(S\).
- Principe extrémal : on part de la plus petite échelle \(d\) entre deux éléments et d'une chaîne maximale de voisins consécutifs à l'échelle \(d\), dont on sépare les éléments d'indice pair et impair.
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2019 (une solution et deux remarques).
Réponse : la taille maximale de \(\mathcal F\) est \(2^k\).
Remarque commune. Par commodité, on appelle échelle entre deux réels \(x\) et \(y\) l'entier \(D(x,y)\).
Solution¶
Construction. L'ensemble \(\mathcal F = \{0, 1, 2, \ldots, 2^k - 1\}\) a \(2^k\) éléments, et l'échelle entre deux de ses éléments est dans \(\{0, 1, \ldots, k-1\}\) (leur différence est entre \(1\) et \(2^k - 1\)). Chaque élément a donc au plus \(k\) échelles.
Majoration. Pour tout ensemble fini \(S\) de réels et tout réel \(x\), notons \(r_S(x)\) le nombre d'échelles distinctes de \(x\) dans \(S\), c'est-à-dire \(r_S(x) = \big|\{D(x,y) : y \in S, y \neq x\}\big|\). Pour tout \(x \in \mathcal F\), on a \(r_{\mathcal F}(x) \leq k\). La majoration \(|\mathcal F| \leq 2^k\) découle immédiatement du lemme suivant (car alors \(|\mathcal F|\, 2^{-k} \leq w(\mathcal F) \leq 1\)). Précision ajoutée : si \(\mathcal F\) était infini, on appliquerait le lemme à une partie finie de \(\mathcal F\) à \(2^k + 1\) éléments, dans laquelle chaque élément a encore au plus \(k\) échelles.
Lemme. Soit \(S\) un ensemble fini de réels et
Alors \(w(S) \leq 1\).
Preuve. Récurrence sur \(n = |S|\). Si \(S = \{x\}\), alors \(r_S(x) = 0\) et \(w(S) = 1\).
Supposons \(n \geq 2\) et notons \(x_1 < \cdots < x_n\) les éléments de \(S\). Soit \(d\) la plus petite échelle entre deux éléments distincts de \(S\) ; il existe des voisins \(x_t\), \(x_{t+1}\) avec \(D(x_t, x_{t+1}) = d\). Pour tous indices \(i\), \(j\) avec \(j - i > 1\), on a \(D(x_i, x_j) > d\), car
Choisissons le plus petit \(i \leq t\) et le plus grand \(j \geq t + 1\) tels que
Soit \(E\) l'ensemble des \(x_s\) d'indice \(s\) pair avec \(i \leq s \leq j\), \(O\) celui des \(x_s\) d'indice impair avec \(i \leq s \leq j\), et \(R\) le reste des éléments (\(S\) est la réunion disjointe de \(E\), \(O\) et \(R\)). Posons \(S_O = R \cup O\) et \(S_E = R \cup E\). On a \(|S_O| < |S|\) et \(|S_E| < |S|\), donc \(w(S_O) \leq 1\) et \(w(S_E) \leq 1\) par hypothèse de récurrence.
Évidemment \(r_{S_O}(x) \leq r_S(x)\) et \(r_{S_E}(x) \leq r_S(x)\) pour tout \(x \in R\), donc
D'autre part, pour tout \(x \in O\), il n'existe aucun \(y \in S_O\) tel que \(D(x, y) = d\) (tous les candidats dans \(S\) étaient dans \(E\)). Donc \(r_{S_O}(x) \leq r_S(x) - 1\), et
De même,
En combinant :
ce qui achève la récurrence. \(\square\)
La taille maximale de \(\mathcal F\) est donc \(2^k\). \(\blacksquare\)
Remarques¶
Remarque 1. Les ensembles \(O\) et \(E\) ne sont pas les seuls possibles. On peut aussi prendre pour \(d\) la plus grande échelle entre deux éléments de \(S\), c'est-à-dire \(d = D(x_1, x_n)\), puis \(O = \{x \in S : D(x, x_n) = d\}\) (une partie « gauche ») et \(E = \{x \in S : D(x_1, x) = d\}\) (une partie « droite »). Ces deux ensembles sont disjoints et non vides (ils contiennent respectivement \(x_1\) et \(x_n\)), et la suite de la preuve est la même.
Remarque 2. Une autre construction de \(2^k\) éléments vient d'un arbre binaire de hauteur \(k\) : on attribue un réel à chaque feuille, en essayant de faire dépendre l'échelle entre deux feuilles seulement de leur distance dans l'arbre. Précisément : \(F_0 = \{0\}\) et \(F_{k+1} = F_k \cup \{x + 3 \cdot 4^k : x \in F_k\}\) (chaque moitié de \(F_{k+1}\) est une copie de \(F_k\)). On a \(F_k \subset [0, 4^k)\) (le livret écrit \([0, 4^{k+1})\) ; il faut \([0, 4^k)\) pour la suite, ce qui est vrai car \(\max F_k = 4^k - 1\)), donc deux éléments de moitiés différentes de \(F_{k+1}\) diffèrent d'une quantité dans \((2 \cdot 4^k, 4 \cdot 4^k) = (2^{2k+1}, 2^{2k+2})\). Par récurrence, chaque élément de \(F_{k+1}\) a \(k\) échelles dans sa propre moitié et la seule échelle \(2k + 1\) dans l'autre moitié.
Dans ces deux constructions, chaque élément a exactement \(k\) échelles ; c'est forcé (à une petite perturbation près) pour tout ensemble maximal. En effet, si un élément \(x\) n'avait que \(k - 1\) échelles (les autres en ayant au plus \(k\)), on prendrait \(\varepsilon > 0\) et \(\mathcal F' = \{y : y \in \mathcal F, y \leq x\} \cup \{y + \varepsilon : y \in \mathcal F, y \geq x\}\). Alors \(|\mathcal F'| = |\mathcal F| + 1\) et, pour \(\varepsilon\) assez petit, aucun élément de \(\mathcal F'\) n'a plus de \(k\) échelles. Cette observation peut motiver l'idée de pondérer les éléments d'un ensemble selon leur nombre d'échelles.
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2022 C1 ★☆☆☆☆ : Dans toute suite de \(\pm 1\), une sous-suite à sauts d'au plus \(2\) a une somme au moins \(C\) en valeur absolue : quel \(C\) ?
- 2014 N1 ★★☆☆☆ : Quel est le plus grand entier qu'on ne peut pas écrire comme somme de nombres \(2^n - 2^k\) ?
- 2024 C8 ★★★★★ : On noircit un carré \(2 \times 2\) qui contient une seule case noire : pour quels \(n\) peut-on tout noircir ?
- 2009 C7 ★★★★★ · OIM P6 : Une sauterelle peut ordonner ses sauts de longueurs distinctes pour éviter \(n\) points interdits.