Notre suite récente de puzzles présentait l'humble balance à double plateau, historiquement un symbole du commerce et du gouvernement, de l'art et de la science. Les balances sont également populaires en mathématiques récréatives. Les énigmes d’équilibre nécessitent un raisonnement clair et logique et se prêtent bien à la généralisation mathématique. Voyons comment Quanta les lecteurs ont équilibré ces qualités dans les énigmes ci-dessous.
Puzzle 1
Vous avez huit pièces identiques. L'un est contrefait et plus léger que les autres, qui ont des poids identiques. Trouvez la mauvaise pièce en deux pesées. Trouvez la formule générale du nombre maximum de pièces pour lesquelles vous pouvez trouver la contrefaçon dans x pesées.
Aborder une version simple d’un problème révèle souvent la clé de la solution. Dans ce cas, imaginez que vous n’avez que trois pièces, dont une plus légère que les deux autres. Si vous comparez l’un d’entre eux à l’un des deux autres, soit ils s’équilibreront, soit ils ne s’équilibreront pas. Si ce n’est pas le cas, vous savez lequel est le plus léger. S’ils s’équilibrent, alors le troisième est le plus léger. Vous n’avez besoin que d’une seule pesée.
Ainsi, dans ce puzzle, si vous parvenez à isoler un groupe de trois (ou moins) contenant la pièce légère lors de la première pesée, vous n'aurez besoin que d'une pesée supplémentaire. Vous pouvez le faire en équilibrant trois n’importe lesquels contre trois autres. Si les deux groupes sont déséquilibrés, vous avez trouvé le groupe contenant le léger et pouvez procéder comme ci-dessus pour la deuxième pesée. S’ils s’équilibrent, pesez simplement les deux pièces restantes l’une par rapport à l’autre et vous trouverez la plus légère.
Notez que cela fonctionne également s’il y en a trois dans le groupe non pesé, nous aurions donc pu commencer avec neuf pièces. En suivant cette logique, et en commençant avec trois pièces, pour chaque pesée supplémentaire, nous pouvons trouver la pièce légère en trois fois le nombre de pièces que nous avions auparavant. La formule nous donnant le nombre maximum de pièces n in w les pesées sont donc n = 3w.
Puzzle 2
Vous avez 12 pièces identiques. L'un est plus lourd ou plus léger que les autres, qui ont des poids identiques.
-
Trouvez la mauvaise pièce en trois pesées.
-
Quel est le nombre maximum de pièces pour lesquelles vous pouvez trouver la mauvaise sur quatre pesées ? Décrivez comment vous trouveriez la fausse pièce.
La solution à cette énigme a été bien décrite par Ted, qui a également montré que l'on peut réellement détecter la mauvaise pièce parmi 13 pièces en trois pesées. Voici la solution de Ted (avec des indentations pour séparer les trois pesées dans chaque cas) :
Commencez par peser 4 pièces contre 4 pièces.
Cas 1 : En cas de déséquilibre, pour la deuxième pesée, mettez 2 de chaque côté le plus lourd des deux côtés de la balance ainsi que 1 de chaque côté le plus léger.
1a : En cas de déséquilibre, la mauvaise pièce est soit les 2 pièces toujours du côté lourd, soit la seule pièce toujours du côté clair.
Pesez les 2 pièces lourdes possibles, la mauvaise est soit la plus lourde des deux, soit l'unique légère si elles sont équilibrées.
1b : Si la deuxième pesée est équilibrée, la mauvaise pièce est l'une des 2 inutilisées du côté le plus clair de la première pesée.
Pesez-les les uns par rapport aux autres, le plus léger est mauvais.
Cas 2 : Si elle est équilibrée, la mauvaise pièce est l'une des 5 restantes. Pesez-en 3 contre 3 déjà pesés (qui sont connus pour être bons).
Cas 2a : En cas de déséquilibre, vous savez que la mauvaise pièce fait partie de ces 3 et si elle est légère ou lourde.
La troisième pesée est constituée de 2 de ces pièces l’une contre l’autre – si elle est déséquilibrée, cela identifie la mauvaise pièce, si elle est équilibrée, c’est la dernière des trois.
Cas 2b : Si la deuxième pesée est équilibrée, la mauvaise pièce est l'une des 2 restantes.
Pesez l’un ou l’autre par rapport à une pièce de monnaie connue. Si ce résultat est déséquilibré, cette nouvelle pièce est mauvaise et vous savez si elle est lourde ou légère. Si ce résultat est équilibré, la 13ème pièce est mauvaise, mais on ne sait pas si elle est lourde ou légère (ce que nous n’avons pas besoin de savoir, donc c’est fini).
Ted a également montré que le nombre maximum de pièces pour quatre pesées est de 40. La formule de ce puzzle est la suivante : n = (3w −1)/2.
Pour les énigmes restantes, les formules généralisées sont encore à l'étude par des mathématiciens professionnels et font l'objet d'articles publiés, dont certains ont été cités par Rainer au printemps. Je me limiterai aux solutions pour les petits nombres de pièces que nous considérons dans les énigmes et ne mentionnerai que les généralisations qui découlent naturellement des méthodes utilisées dans ces cas.
Puzzle 3
Il s'agit d'une variante du puzzle 1. Vous avez à nouveau huit pièces identiques, dont l'une est plus légère que les autres. Cependant, vous avez maintenant trois échelles. Deux des échelles fonctionnent, mais la troisième est cassée et donne des résultats aléatoires (elle est parfois juste et parfois fausse). Vous ne savez pas quelle échelle est cassée. Combien de pesées faudra-t-il pour trouver la pièce lumineuse ?
Comme nous l’avons vu dans le problème 1, il suffit de deux pesées avec une bonne balance. Nous savons aussi que les deux bonnes balances conviendront toujours, donc si nous répétons simplement chaque pesée sur les trois balances, nous aurons la réponse en six pesées comme l'a suggéré un lecteur. Si nous essayons de le faire sur un plus petit nombre de pesées, cela devient un peu délicat. Nous ne pouvons pas identifier une bonne balance simplement en pesant les mêmes pièces sur deux balances, car même si elles concordent, l’une ou l’autre peut toujours être une mauvaise balance. (Cela montre également avec quelle facilité la désinformation ou les informations aléatoires peuvent obscurcir la vérité.)
En fait, ce problème peut être résolu très intelligemment en seulement quatre pesées ! Rainer au printemps a publié la solution en utilisant une notation nouvelle qui semble avoir été créée pour ce puzzle. Mais avant d’y aller, je veux que vous imaginiez un scénario qui, je l’espère, rendra les choses plus intuitives.
Imaginez que vous êtes un détective enquêtant sur un délit de fuite dans un petit pays dont les voitures ont des plaques d'immatriculation à deux chiffres utilisant uniquement les chiffres 0, 1 et 2. Trois personnes, A, B et C, ont observé l'incident. Deux d’entre eux répondent toujours correctement à une question à trois choix et un donne des réponses complètement aléatoires. Vous ne savez pas qui est le répondant aléatoire. Vous devez poser à chacun d’eux une seule question à trois choix, puis choisir celui qui dit définitivement la vérité pour obtenir plus d’informations.
Voici comment procéder. Demandez à A si le premier chiffre est 0, 1 ou 2. Disons que A dit 2. Demandez à B si le deuxième chiffre est 0, 1 ou 2. Disons que B dit 1. Demandez ensuite à C de faire un choix entre ces trois affirmations :
- Seul A dit la vérité.
- Seul B dit la vérité.
- Les deux disent la vérité.
Vous pouvez croire celui que C vous dit et interroger cette personne sur l’autre chiffre. Pour comprendre pourquoi, considérons que si A ment, alors C est fiable et dira que B dit la vérité. Le deuxième chiffre sera en fait 1 et vous pourrez alors interroger B sur le premier chiffre. De même, si B ment, alors C est à nouveau fiable et dira que A dit la vérité. Alors le premier chiffre est en fait 2 et vous pouvez interroger A sur le deuxième chiffre. Enfin, si C ment, alors A et B sont fiables, vous pouvez donc toujours croire et choisir celui à qui C dit. (Et si C dit que A et B disent la vérité, alors ils doivent tous les deux le dire.) La clé ici est que votre choix de questions ne permet pas à C de mentir de manière à jeter le doute sur A et B. Puisqu’au moins l’un des éléments A et B doit être fiable, vous pouvez toujours choisir celui avec lequel C est d’accord, même s’il ne s’agit que d’une réponse aléatoire. Si les trois sont d’accord, alors vous possédez déjà les deux chiffres de la plaque d’immatriculation.
Voici comment traduire cette histoire dans notre puzzle. Les échelles sont A, B et C. Vous pouvez traduire les deux chiffres de la plaque d'immatriculation en pièces comme suit : 01 est la pièce 1, 02 est la pièce 2, 10 est la pièce 3, 11 est la pièce 4, 12 est la pièce 5, 20 est la pièce 6, 21 est la pièce 7 et 22 est la pièce 8. Les lecteurs avisés reconnaîtront qu'il s'agit du système numérique de base 3 (ou ternaire). Notez également qu'il existe un nombre supplémentaire possible 00, que vous pouvez utiliser pour une neuvième pièce pour laquelle cette technique fonctionnera également, comme dans le puzzle 1.
Pour la première pesée, vous divisez les pièces par leur premier chiffre (base 3), vos trois groupes seront donc les pièces [1, 2], [3, 4, 5] et [6, 7, 8]. Pesez [3, 4, 5] contre [6, 7, 8] sur la balance A. Si A fonctionne bien, vous aurez le bon premier groupe de chiffres comme dans l'énigme 1. De même, pour la deuxième pesée sur la balance B, vos groupes seront ceux avec le même deuxième chiffre : [1, 4, 7], [2, 5, 8] et [3, 6]. Si B fonctionne bien, vous aurez le bon deuxième chiffre. Pour la troisième pesée, sur la balance C, vous pesez le groupe identifié par A par rapport au groupe identifié par B. En suivant notre exemple, pour 21, les groupes seront [6, 7, 8] et [1, 4, 7]. La pièce 7 ne peut pas être placée des deux côtés en même temps, nous la laissons donc de côté et pesons [6, 8] et [1, 4] l'un contre l'autre. Notez que si A et B sont tous deux fiables, alors 7 est en fait la bonne réponse, et peu importe quel côté sort le plus léger sur C. Si par hasard la pesée sur C est équilibrée, alors les trois balances sont d'accord, et vous avez votre réponse (pièce 7) en seulement trois pesées. Si A est fiable et B ne l'est pas, la pièce la plus légère est dans [6, 8], quelle échelle C confirmera, et si B est fiable et A ne l'est pas, la pièce la plus légère est dans [1, 4], quelle échelle C confirmera également.
Ainsi, en trois pesées, nous avons soit identifié la pièce légère, soit l'avons réduite à un groupe de deux, et nous avons également identifié une balance fonctionnelle. La quatrième pesée sur la balance A ou sur la balance B (selon la balance acceptée par C) fera le reste.
Cette solution me semble incroyablement belle !
Cette méthode peut être généralisée pour trouver la pièce légère parmi 32x pièces en 3x + 1 pesée avec le jeu de balance donné. Il vous faudra donc sept pesées pour 81 pièces. Pour un plus grand nombre de pièces (>~1,000 XNUMX), une solution encore plus efficace existe.
Puzzle 4
Vous disposez de 16 pièces dont huit lourdes et de même poids. Les huit autres sont légers et du même poids. Vous ne savez pas quelles pièces sont lourdes ou légères. Les pièces semblent identiques à l'exception d'une qui a des marques spéciales. Avec une bonne balance, pouvez-vous déterminer si la pièce spéciale est légère ou lourde en trois pesées ? Quel est le nombre maximum de pièces avec lesquelles vous pouvez commencer et résoudre ce problème avec succès en quatre pesées ?
À première vue, ce puzzle semble presque impossible à réaliser en trois pesées, comme l'a conclu un de nos lecteurs. Néanmoins, avec un peu d'ingéniosité, cela peut être fait, et les deux Ted ainsi que Rainer au printemps apporté des solutions correctes. Ted a fourni quelques principes généraux inestimables auxquels il convient de prêter attention.
Premièrement, jusqu’à ce que vous obteniez un résultat déséquilibré lors d’une pesée, vous n’aurez pas suffisamment d’informations pour déterminer si la pièce spéciale est lourde ou légère. Il faut donc essayer de forcer un résultat déséquilibré.
Deuxièmement, si vous obtenez un résultat équilibré (par exemple, la pièce spéciale A équilibre la pièce B), vous pouvez combiner les pièces qui sont équilibrées et les peser avec deux autres pièces, C et D. Si elles sont déséquilibrées, vous avez la réponse ; sinon, vous avez maintenant doublé le nombre de pièces similaires, ce qui pourrait vous aider à obtenir une réponse déséquilibrée lors de la prochaine pesée. Vous pouvez également effectuer ce processus à l'envers avec des nombres de pièces puissances de deux (4, 8, etc.) si vous obtenez un résultat initial déséquilibré comme le montre la solution suivante.
Vous trouverez ci-dessous toute la procédure permettant d'identifier le type de la pièce spéciale A dans tous les cas en trois pesées. (B, C et D sont trois pièces placées du même côté que A dans le poids 1 (W1) ; X et Y sont les deux pièces non utilisées dans W1.)
Ce puzzle a été inventé par le mathématicien russe Constantin Knop, une autorité mondiale en matière de puzzles de pesée de pièces. Beaucoup de ses articles sont en russe, mais vous pouvez trouver plusieurs puzzles de pièces de monnaie (entre autres puzzles intéressants) sur le site blogue de sa collaboratrice Tanya Khovanova.
Quant à la généralisation, je vous laisse voir si cette même méthode fonctionne pour trouver le type d’une pièce spéciale parmi 32 pièces, dont 16 lourdes et 16 légères.
Puzzle 5
Vous avez n des pièces d'apparence identique, dont certaines sont contrefaites et plus légères que les autres. Tout ce que vous savez, c'est qu'il existe au moins une pièce contrefaite et qu'il y a plus de pièces normales que de pièces contrefaites. Votre travail consiste à détecter toutes les pièces contrefaites.
Le fait qu’il y ait au moins une pièce légère et qu’il y ait plus de pièces normales que de pièces légères rend ce puzzle moins complexe qu’il n’y paraît à première vue, du moins pour les petits nombres. Regardons les nombres de pesées pour une à huit pièces.
Pour une et deux pièces, il ne peut y avoir de pièces légères selon la deuxième condition, donc aucune pesée n'est requise.
Trois pièces : Une seule pièce légère. Une pesée requise par puzzle 1.
Quatre pièces : Une seule pièce légère. Une pesée supplémentaire nécessaire, donc w = 2.
Cinq pièces : Une à deux pièces légères. C'est le premier cas intéressant. La question est : devrions-nous peser une pièce contre une, ou deux pièces contre deux ?
Si nous pesons un contre un, nous pouvons avoir :
- Deux pesées déséquilibrées : Deux pièces découvertes ; nous avons fini.
- Une pesée équilibrée sur deux : Les pièces équilibrées doivent être normales, donc la dernière pièce nécessite une autre pesée, w = 3.
- Deux pesées équilibrées : Lors de la troisième pesée, pesez une pièce de chaque pesée précédente par rapport à une autre. S'ils sont équilibrés, tous les quatre sont normaux et la pièce 5 est la pièce claire. Nous avons fini; w = 3 encore. Si elles sont déséquilibrées, nous avons retrouvé les deux pièces légères, et nous avons terminé en trois pesées.
Si, au contraire, nous pesons deux contre deux, nous avons encore besoin de trois pesées, car nous devons distinguer les possibilités selon lesquelles les pièces peuvent être différentes ou similaires d'un côté ou de l'autre. Les pesées utilisant un petit nombre de pièces regroupées ne semblent présenter aucun avantage par rapport aux pesées avec des pièces uniques.
Cela se vérifie pour :
Six pièces : Une à deux pièces légères ; w = 4.
Sept pièces : Une à trois pièces légères ; w = 5.
Huit pièces : Une à trois pièces légères ; w = 6. Cette solution a une structure simple :
- Faites d’abord quatre pesées d’une pièce contre la suivante. Toutes les pièces sont utilisées.
- Dans le pire des cas : les quatre pesées sont équilibrées (il y a deux pièces légères qui s'équilibrent).
- Deux pesées suivantes : Peser une pièce de monnaie du poids 1 contre une pièce du poids 2 ; de même, pesez une pièce de monnaie pesant 3 contre une pièce de monnaie pesant 4.
- L'une de ces pesées sera déséquilibrée, identifiant les deux pièces légères. Nous avons terminé en six pesées.
Désolé, notre séquence de 0, 0, 1, 2, 3, 4, 5, 6 n'est certainement pas assez intéressante pour être soumise au Encyclopédie en ligne des séquences entières!
As Jonas Togersen Kjellstadli souligné, la solution semble être w = n − 2 pour les petits nombres, mais nous n’avons pas prouvé que cela ne changera pas pour les grands nombres. À certains n, l'utilisation de plusieurs pesées de pièces pourrait commencer à faire mieux, ou plus de pesées que n − 2 peuvent être nécessaires. Nous pouvons simplement généraliser la solution pour huit pièces à toutes puissances de 2, ce qui donne n − 2 comme borne supérieure du nombre de pesées pour toutes les puissances de 2.
Mark Pearson a discuté de la similitude de ce problème avec les codes correcteurs d'erreurs et a suggéré d'utiliser une approche fondée sur la théorie de l'information basée sur le nombre de résultats possibles. En utilisant une telle approche, Mike Roberts a affiché une limite inférieure pour le cas plus général, qui Rainer au printemps dérivé une approximation pour. Rainer a également posté un limite supérieure à partir d'un article publié, mais a noté que les limites ne sont pas nettes pour les faibles n et donc inutile pour les petits nombres que nous avons considérés ci-dessus. Ainsi, pour sept pièces, les limites citées donnent une fourchette de 4 à 16, entre laquelle se situe notre réponse, 5. J. Payette donne des références mathématiques supplémentaires et des limites pour toutes les énigmes.
Merci à tous ceux qui ont participé. Le prix Insights de ce mois est décerné conjointement à Ted et Rainer aus dem Spring. Toutes nos félicitations!
A la prochaine fois pour du nouveau ACTUALITES.
