Petites enigmes > Réponse Sciences sujet

Uncurieux a écrit :

> (en espérant que ce soit clair)

Oui ça l'est.

Pour ceux qui préfèrent une démonstration uniquement en combinatoire, sans graphe (c'est exactement la même démo, c'est juste les outils qui changent) :

Déjà en reprenant les notations que j'ai introduite, on considère qu'il existe une fonction f résolvant le problème. On va noter E l'ensemble de toutes les positons du plateau (il a 2^n éléments), et E_i = {Y | f(Y) = i}. On va montrer que le cardinal de E_i est exactement 2^n/n (ce qui prouvera que 2^n/n est entier : un cardinal est toujours entier).

On choisit un i. pour n'importe quel Y dans E_i, {X | X est à un mouvement de Y} a pour cardinal n (on a n mouvements, qui mènent à les position différentes). Par ailleurs, la réunion suivante :
U_(Y élément de E_i) {X | X est à un mouvement de Y}
est égale à E : toute position est à un mouvement d'une position renvoyant i. Le cardinal d'un union est inférieur à la somme des cardinaux :
somme_(Y élément de E_i) card {X | X est à un mouvement de Y} >= 2^n
et somme_(Y élément de E_i) card {X | X est à un mouvement de Y} = somme_(Y élément de E_i) n = n * card E_i
L'on en ressort n * card E_i >= 2^n, soit card E_i >= 2^n/n.

Par ailleurs, U_i E_i = E, et il s'agit d'une union disjointe ; le cardinal de E est donc exactement la somme des cardinaus des E_i :
2^n = somme_(i entre 0 et n-1) card E_i >= somme_(i entre 0 et n-1) 2^n/n = n* 2^n/n = 2^n
Le seul cas d'égalité possible dans la précédente inégalité correspond au cas où chaque card E_i vaut exactement 2^n/n.

On a donc établi que 2^n/n est entier. La fin est de l'arithmétique de base : les seuls diviseurs de 2^n sont les puissance de 2.