Exercice 13

On considère l'application $$\chi : S \to \{0, 1\}^{m}, \qquad x \mapsto \big(\mathbf{1}_{A_{1}}(x), \dots, \mathbf{1}_{A_{m}}(x)\big).$$ Elle est injective : si $x \neq y$, il existe $i$ tel que $A_{i}$ contienne l'un des deux éléments et pas l'autre, c'est-à-dire tel que $\mathbf{1}_{A_{i}}(x) \neq \mathbf{1}_{A_{i}}(y)$, et les images de $x$ et de $y$ diffèrent par leur $i$-ième coordonnée. Par le chapitre 2, théorème 2, et la proposition 2 (iv), on a $n \leqslant 2^{m}$, et la croissance du logarithme donne $\ln n \leqslant m\ln 2$. $$\boxed{m \geqslant \frac{\ln n}{\ln 2}}$$ Pour l'égalité, on prend $S = \{0, 1\}^{m}$, qui a $n = 2^{m}$ éléments, et $A_{i} = \{x \in S \mid x_{i} = 1\}$ pour $i \in \llbracket 1\,,m \rrbracket$. Deux éléments distincts de $S$ diffèrent par une coordonnée $i$, et $A_{i}$ contient l'un et pas l'autre : les $A_{i}$ séparent les points, et $m = \frac{\ln n}{\ln 2}$. Pour $m = 3$, on sépare ainsi les huit éléments de $\{0, 1\}^{3}$ avec trois parties.

On peut le lire comme un jeu de questions : pour identifier un élément inconnu de $S$, on pose les questions « appartient-il à $A_{i}$ ? », auxquelles on répond par oui ou non. Les parties séparent les points si et seulement si les réponses déterminent l'élément, et il faut au moins $\frac{\ln n}{\ln 2}$ questions, nombre de chiffres de l'écriture de $n$ en base $2$, à un près. C'est le principe de la recherche dichotomique, qui atteint ce minimum.