icone-challenge-math-OS

Pour toute partie B de E, notons 1_{B} sa fonction indicatrice.

On rappelle que, par définition :

    \[ 1_{B}:E\rightarrow\left\{0,1\right\} ,\thinspace x\mapsto\left\{\begin{array}{cc} 1 & \text{si }x\in B\\ 0 & \text{sinon} \end{array}\right.\]

L’hypothèse dit exactement que l’application :

    \[ \varphi:E\rightarrow\left\{0,1\right\} ^{m},\thinspace x\mapsto\left(1_{A_{1}}\left(x\right),\cdots,1_{A_{m}}\left(x\right)\right)\]

est injective. Par conséquent \text{card}\left(E\right)\leqslant\text{card}\left(\left\{0,1\right\} ^{m}\right), c’est-à-dire n\leqslant2^{m}.

Vu que m est entier, cette dernière inégalité équivaut à :

    \[\boxed{m\geqslant\left\lceil \log_{2}\left(n\right)\right\rceil}\]

Afin de montrer que cette minoration de m est optimale, utilisons le théorème donnant l’existence et l’unicité, pour un entier naturel non nul, de son écriture en base 2.

Si nécessaire, consulter les vidéos Système de numération – 1 et Système de numération – 2, où cette question est étudiée en détail.

Afin de simplifier la présentation, supposons que n=2^{p} pour un certain p\in\mathbb{N}. Ce qui suit pourrait être facilement adapté si n n’est pas une puissance de 2.

On peut considérer, sans perte de généralité, que :

    \[ \boxed{E=\left\{0,\cdots,2^{p}-1\right\}}\]

Chaque entier k\in E possède une écriture binaire, de la forme :

    \[ k=\sum_{i=0}^{p-1}b_{i}\left(k\right)\thinspace2^{i}\qquad\text{avec }b_{i}\left(k\right)\in\left\{0,1\right\} \text{ pour tout }i\]

Considérons alors, pour tout i\in\left\{0,\cdots,p-1\right\}, l’ensemble :

    \[ A_{i}=\left\{k\in E;\thinspace b_{i}\left(k\right)=1\right\} \]

Les ensembles A_{0},\cdots,A_{p-1} sont des parties distinctes de E. En effet, si 0\leqslant i,j\leqslant p-1 et i\neq j, alors 2^{i}\in A_{i} mais 2^{i}\notin A_{j}, donc A_{i}\neq A_{j}.

En outre, étant donnés deux entiers k\neq k' dans \left\{0,\cdots,2^{p}-1\right\} , leurs écritures binaires diffèrent, donc il existe i\in\left\{0,\cdots,p-1\right\} tel que b_{i}\left(k\right)\neq b_{i}\left(k'\right). Autrement dit :

    \[\exists i\in\left\{0,\cdots,p-1\right\} ;\thinspace\begin{array}{cc}\mid & k\in A_{i}\text{ et }k'\notin A_{i}\\\text{ou}\\\mid & k\notin A_{i}\text{ et }k'\in A_{i}\end{array}\]


On a donc construit une famille de p=\left\lceil \log_{2}\left(n\right)\right\rceil parties de E possédant la propriété voulue.

Pour consulter l’énoncé, c’est ici

Partager cet article
  •  
  •  
  •  
  •  

Laisser un commentaire