Il y a 24 situations possibles (l’homme différent peut être l’un des 1-12, et il peut être plus lourd ou plus léger). Ainsi, nous devons enregistrer224 bits d’informations pour résoudre le puzzle. Vous pouvez peser trois combinaisons d’hommes sur la scie à scie. Chaque pesée peut donner 3 réponses possibles: côté gauche plus lourd, côté droit plus lourd, ou les deux côtés égaux. Ainsi, en principe, nous pouvons obtenir log227 bits à partir des trois comparaisons. Donc, en principe, nous devrions être en mesure de résoudre le problème. La clé de ce problème est de s’assurer que les trois valeurs de sortie (côté gauche plus lourd, côté droit plus lourd, deux côtés identiques) sont possibles et informatives dans presque toutes les comparaisons que vous faites afin que nous puissions extraire 224 bits des comparaisons. Notez que cela implique que la première comparaison doit rapporter plus de 1 bit d’information. Cela suggère que nous essayons de maximiser la quantité d’informations que nous pouvons obtenir à partir de la première comparaison, en rendant les trois résultats également probables. Comparer (1,2,3,4) à (5,6,7,8) fait exactement cela. Une logique similaire nous aidera à concevoir toutes les comparaisons supplémentaires.
Voici une solution:
Numéroter les hommes 1,2,3…12. Pesez d’abord 1,2,3,4 contre 5,6,7,8. L’une des deux choses se produira:
1) Elles sont égales. Maintenant, nous savons que l’homme différent est parmi {9,10,11,12}. Peser 9,10,11 contre 1,2,3. Si ceux-ci sont égaux, l’homme différent a 12 ans. Pesez 12 contre 1 pour savoir si 12 est heaver ou plus léger. Si le 9,10,11 diffère de 1,2,3, pesez 9 contre 10. S’ils sont les mêmes, l’homme différent est 11, et il est plus lourd si 9,10,11 était plus lourd que 1,2,3 et il est plus léger si 9,10,11 était plus léger que 1,2,3. Si 9 et 10 sont différents, l’homme différent est le plus léger de la comparaison 9,10 si 9,10,11 était plus léger que 1,2,3 (et il est plus léger); l’homme différent est le plus lourd de la comparaison 9,10 si 9,10,11 était plus lourd que 1,2,3 (et il est plus lourd).
2)Ils sont différents. Sans perte de généralité, supposons que 1,2,3,4 soit plus lourd que 5,6,7,8. (Nous pourrions toujours réétiqueter les hommes pour que cela soit vrai). Nous savons que {9,10,11,12} pèsent tous le même poids.
Peser 1,2,5,6,7 contre 8,9,10,11,12:
a)Si 1,2,5,6,7 est plus lourd, alors 1 ou 2 plus lourd, ou 8 est plus léger. Peser 1 contre 2. S’ils sont différents, le plus lourd des deux est celui que nous recherchons (et le plus lourd). S’ils sont les mêmes, 8 est celui que nous recherchons (et plus léger).
b)Si 1,2,5,6,7 est plus léger, alors l’un des 5,6,7 est différent et plus léger. Peser 5 contre 6. S’ils sont différents, le plus léger des deux est celui que nous recherchons (et plus léger). S’ils sont identiques, 7 est différent (et plus léger).
c) S’ils sont identiques, alors l’un des 3,4 est différent. Pesez-les l’un contre l’autre. Celui qui est le plus lourd est l’homme différent (et le plus lourd).