Je n’ai rien compris à l’énigme 4, quelqu’un saurait m’expliquer ?
Pour la 5, c’est une application marrante du théorème de Hall ! (Chercher « Hall’s marriage card trick » sur google.)
Pour la 3, je n’ai pas eu le courage de lire la solution, mais on peut faire plus simple (au moins dans la présentation).
On cherche une stratégie à 3 pesées. Pour simplifier, on considère que ces pesées sont indépendantes : les pièces pesées ne dépend pas des résultats précédents. Les trois pesées donnent un triplet (a,b,c) avec a, b, c des entiers entre -1 et 1, suivant quel côté était plus lourd ou s’ils avaient le même poids.
Chaque pièce devra donc être identifiée de manière unique par ce triplet. Comme on ne sait pas si la pièce recherchée est plus lourdre ou plus légère que les autres, le triplet (a,b,c) doit identifier la même pièce que le triplet (-a,-b,-c). On n’a donc plus que $\frac{3^2 - 1}{2} - 1 = 14$ identifiants possibles (car -(0,0,0) = (0,0,0)).
Les identifiants possibles (modulo $x \mapsto -x$) sont les suivants (énumération classique en base 3 mais on veut que le premier chiffre soit 1).
| 0 0 0 0 0 1 1 1 1 1 1 1 1 1
0 0 1 1 1 0 0 0 1 1 1 -1 -1 -1
0 1 0 1 -1 0 1 -1 0 1 -1 0 1 -1
|
Une stratégie est un tableau de -1, 0 et 1. Chaque ligne correspond à une pesée et chaque colonne correspond à une pièce. Le nombre à la ligne i et la colonne j dit de quel côté on doit mettre la pièce j à la pesée i.
On doit aussi mettre le même nombre de pièces de chaque côté à chaque pesée.
En hasardant un peu, on peut trouver la stratégie suivante :
| 0 0 0 0 1 1 1 1 -1 -1 -1 -1 0
0 1 -1 0 0 1 -1 0 1 -1 0 1 -1
0 0 1 -1 0 0 1 -1 0 1 -1 1 -1
|
Avec la colonne de zéros, ça fait 13 pièce au lieu des 12 de l’énigme. Si on veut savoir si la fausse pièce est plus lourde ou plus légère que les autres, alors il faut retirer (0,0,0).
On peut même généraliser. On a un sous-espace d’un espace vectoriel réel, et puis on veut trouver ses points dont les coordonnées sont dans {-1,0,1}… Mais je ne sais pas si ça mène à grand chose.
Généralisation de l’énigme : montrer qu’on peut traiter $\frac{3^n - 1}{2}$ pièces en $n$ pesées (et que c’est le nombre maximal de pièces qu’on peut traiter en $n$ pesées). [ajout] Le nombre maximal avec une stratégie qui ne fait pas dépendre les pesées des résultats précédents, du moins.
La dernière énigme m’a fait penser à la revue Les nouvelles d’Archimède où j’avais vu un problème similaire (pas le même). C’est la rubrique « Paradoxes » de Jean-Paul Delahaye.
Y’a plein d’énigmes avec des chapeaux, aussi, en voici deux.
- On a $n$ personnes et $n$ couleurs de chapeaux. Chaque personne a sur sa tête un chapeau dont elle ne connaît pas la couleur (mais elle connaît les couleurs disponibles). Chaque personne pense à une couleur, sans la dire aux autres. S’il y a au moins une personne qui a pensé à la couleur de son chapeau, alors c’est gagné, sinon c’est perdu. Déterminer une stratégie pour gagner à coup sûr.
- (Plus connue je crois.) Une infinité dénombrable de personnes sont alignées dans un certain ordre. Les couleurs possibles des chapeaux sont connues à l’avance et en nombre fini. Chaque personne peut voir les couleurs des chapeaux de toutes les autres personnes (et on suppose aussi que ces personnes peuvent manipuler cette quantité infinie d’information comme un tout). Chaque personne doit penser à une couleur, et il doit n’y avoir qu’un nombre fini d’erreurs.
Il y a aussi Des chapeaux, des couleurs et des structures algébriques.
