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)
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
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.