Douze boules et une échelle

Diviser ce i en trois groupes de quatre, A1, A2, A3, A4; B1, B2 …; C1, C2 … Chaque étape correspond ici à une pesée.

• Pesez A contre B.
  • Si A> B, alors pesez A1, B1 et B2 contre B3 , B4 et C1.
    • Si les poids sont égaux, alors lun des A2 … 4 est plus lourd; peser A2 et A3. Sils sont égaux, A4 est plus lourd. Si lun est plus lourd, alors cette balle est la plus lourde.
    • Si le premier groupe est plus lourd, alors soit A1 est plus lourd, soit B3-4 est plus léger. Comparez B3 et B4; sils sont égaux, A1 est plus lourd; sils sont différents, la plus légère est la balle la plus légère.
    • Si le premier groupe est plus léger, alors B1 ou B2 est plus léger. Pesez-les et voyez.
  • Si A < B, renumérotez toutes les balles A en balles B et effectuez ce qui précède étapes.
  • Si A = B, pesez A1, A2, A3 contre C1, C2, C3
    • Sils sont égaux, alors pesez A1 contre C4. Si A1 est plus léger, alors C4 est la balle impaire et elle est lourde. Si A1 est plus lourd, alors C4 est la balle impaire et elle est légère.
    • Si A est plus lourd que C, pesez C1 contre C2. Sils sont égaux, alors C3 est la balle impaire et elle est plus légère. Si elles ne sont pas égales, alors la plus légère des deux balles est la plus légère
    • Si A est plus léger que C, pesez C1 contre C2. Sils sont égaux, alors C3 est la balle impaire et elle est plus lourde. Si elles ne sont pas égales, alors la plus lourde des deux balles est la plus lourde.

Nous pouvons travailler à rebours à partir de la troisième étape pour voir, approximativement, pourquoi cela fonctionne. Lors de la troisième pesée, les options doivent être réduites à deux ou trois balles. Cela signifie que la deuxième pesée doit se réduire à deux ou trois boules possibles.

Nous savons que la première étape supprimera 1/3 ou 2/3 des solutions possibles, quoi que vous fassiez. Cela signifie que, dans le cas 1/3, vous devez diviser les possibilités de 8 en un groupe de 3, un groupe de 3 et un groupe de 2. À partir de là, la troisième pesée indique la balle impaire. Parce que ce cas implique quun jeu de balles est plus lourd, en trouvant la balle impaire, nous savons si elle est plus lourde ou plus légère, nous navons donc pas du tout à nous soucier de cette information.

Dans le cas 2/3, vous devez réduire les possibilités en un groupe de 3 et un groupe de 1, ce qui est assez facile à faire intuitivement. Puisque nous ne connaissons pas le poids relatif de la balle impaire dans ce cas, les informations de la troisième pesée doivent être utilisées pour déterminer si la balle est plus lourde ou plus légère.

Commentaires

• Bien que cette réponse soit correcte, jespérais une réponse qui expliquerait la stratégie derrière les choix des éléments à peser.
• @JoeZ. I ‘ a ajouté un peu comment jai déterminé cette réponse, même si je ‘ ne suis pas sûr de pouvoir parler dune solution générale à ce problème. (Aussi, Pour info, jai ‘ modifié ma réponse à votre autre question.)
• Ce que vous ‘ avez mis en place est Bien. Je pensais au raisonnement plus quà la stratégie, reviens y réfléchir.

Voilà est une autre façon de résoudre ce problème, qui nimplique aucune sorte de branchement conditionnel. Il est en effet possible de définir au préalable un programme de pesée fixe et de toujours déterminer quelle balle est la plus légère ou la plus lourde en seulement 3 pesées. Jexpliquerai comment ci-dessous.

Lessentiel des problèmes comme ceux-ci est, combien dinformations pouvez-vous obtenir de la procédure que vous êtes autorisé à entreprendre? À chaque pesée, la balance peut basculer vers la gauche, basculer vers la droite ou rester équilibrée.Cela vous donne un total de 3 ³ = 27 résultats possibles, et dans ce cas, vous devez en discerner 24 résultats (une des 12 balles est soit légère, soit lourde, soit 12 × 2 = 24 ).

Nous devons donc commencer la tâche fastidieuse de mapper chaque résultat à un résultat.

Lune des choses que nous pouvons immédiatement remarquer est quil y a aussi trois états chaque boule peut se trouver lors de chaque pesée – sur le côté gauche de la balance, sur le côté droit de la balance ou en dehors de la balance. Naturellement, cela correspond aux états de léchelle dune manière qui « est intuitivement analogue:

Si la balle impaire est plus lourde …

• et la balle est placé sur le côté gauche, léchelle basculera vers la gauche.
• et la balle est placée sur le côté droit, léchelle basculera vers la droite.
• et la balle est hors de léchelle, léchelle restera équilibrée.

Si la balle est plus légère, les deux premiers cas sont inversés.

Il y a 27 façons de placer chaque balle dans les trois pesées, chacune correspondant à un résultat différent si cette balle est la balle impaire. Nous devons trouver un arrangement de balles où chaque ensemble possible de placements et son inverse (pour les cas lourds et légers) est distinct – donc non deux boules sont au même endroit pour les trois pesées.

Voici « un arrangement préliminaire qui satisfait la propriété de distinction. Notez quaucun arrangement possible napparaît plus dune fois dans les deux tableaux:

 Normal Inverse Ball 1 2 3 1 2 3 1 L R 2 L R 3 L R 4 L R R L 5 L R R L 6 L R R L 7 L L R R 8 L L R R 9 L L R R 10 L L R R R L 11 L R L R L R 12 R L L L R R L = place it on the left R = place it on the right = leave it off 

Tout de suite, nous nous heurtons au problème que nous ne mettons pas le même nombre de balles sur chaque échelle. Si vous avez sept balles dun côté et une de lautre, la balance va bien sûr basculer sur le côté avec sept balles (à moins que votre balle étrange ne soit ridiculement lourde, mais ne la divertissons pas. scénario). Nous devons donc inverser quelques-unes de ces configurations afin de « mettre quatre de chaque côté pour chaque pesée. Avec quelques essais et erreurs, nous pouvons obtenir quelque chose comme ceci:

 Normal Inverse Ball 1 2 3 1 2 3 1 L R 2 L R 3 R L 4 L R R L 5 R L L R 6 L R R L 7 R R L L 8 L L R R 9 L L R R 10 R R L L L R 11 R L R L R L 12 L R R R L L 

Donc, notre programme final de pesée des balles est le suivant:

Weighing 1: 1 4 8 12 / 5 7 10 11 Weighing 2: 2 6 9 11 / 4 7 10 12 Weighing 3: 5 8 9 10 / 3 6 11 12 

Et les résultats sont interprétés comme tels:

==L : 3L L== : 1H R== : 1L ==R : 3H L=L : 8H R=L : 5H =L= : 2H L=R : 5L R=R : 8L =LL : 9H LL= : 7L RL= : 4L =LR : 6H LLR : 10L RLL : 12L =R= : 2L LR= : 4H RLR : 11H =RL : 6L LRL : 11L RR= : 7H =RR : 9L LRR : 12H RRL : 10H = : scale balanced L : scale tipped to the left R : scale tipped to the right nL : ball n is light nH : ball n is heavy 

Et ainsi, nous « avons créé un système de pesée où chaque pesée est complètement prédéterminée à lavance, qui parvient toujours à déterminer quelle balle est la balle impaire, et si elle est plus légère ou plus lourd.

Vous remarquerez peut-être que nous navons pas utilisé LLL, RRR, ou === dans nos arrangements.

Nous ne pouvons « t utiliser LLL et RRR comme une 13e paire pour une 13e balle, car alors nous finirions par devoir mettre neuf balles sur la balance, et il ny a aucun moyen de le faire puisque neuf est impair. Nous pourrait probablement lutiliser dans lieu de lune des paires LLR/RRL, mais en laissant LLL et RRR out crée une symétrie dans le tableau des résultats que jaime plutôt.

Cependant, ce qui est intéressant, cest que vous pouvez avoir une 13e boule que vous jamais placez-les sur nimporte quelle balance, et si votre balance séquilibre dans les trois pesées, la 13e balle que vous navez jamais pesée est la balle étrange (bien que vous ne puissiez évidemment pas dire sans quune quatrième ne pèse si elle est plus légère ou plus lourde).

Commentaires

• Donc, fondamentalement, on peut résoudre cela avec 13 boules, si on a une boule détalon 14-th. Excellente réponse.
• Probablement même 14 balles, où la 14e balle peut être plus lourde, peut être résolue, mais cest plus difficile, vous pouvez probablement ‘ t.

Certaines des réponses existantes à cette ancienne question sont excellentes, mais il y a une réponse célèbre qui Je pense quil mérite dêtre mentionné ici. Il provient dun article dans Eureka , le magazine annuel de la société étudiante de mathématiques de lUniversité de Cambridge, écrit par CAB Smith sous le pseudonyme de « Blanche Descartes ».

Il a deux fonctionnalités très intéressantes. La première est que cest une solution « sans ramification »: vous navez pas besoin de changer ce que vous faites lors des pesées ultérieures en fonction des résultats des précédentes. La seconde est quune fois que vous lavez vu, il est presque impossible doublier.

La solution de Smith est entièrement écrite en vers et comprend une explication de la façon dont tout cela fonctionne, mais je ne citerai que le réponse réelle. « F » voici notre protagoniste, le professeur Felix Fiddlesticks, dont la mère lui a demandé de laide pour résoudre le casse-tête. Jai apporté quelques modifications minimes au formatage dorigine.

F a placé les pièces dans une rangée
Et a marqué sur chaque lettre une lettre, donc,
Pour former les mots: F AM NOT LICKED
(Un idée dans son cerveau avait cliqué.)

Et maintenant sa mère il « va enjoindre:
 » MA, FAIRE / AIMEZ MOI TO / TROUVER
FAKE / COIN! « 

Chacune des trois lignes de linjonction de F décrit une pesée.Lorsque vous les avez toutes faites, les résultats déterminent de manière unique quelle pièce est fausse et de quelle manière.

Commentaires

• +1. Cest ce que je pense est une version améliorée de la réponse de Joe Z ‘

Jai passé du temps à travailler sur ce puzzle après son apparition sur « Brooklyn Nine-Nine » (si vous le souhaitez, vous pouvez regarder le capitaine Holt décrire le puzzle ici ) et jai écrit une solution détaillée et illustrée ici: Solution de lîle de Tyreses . Dans ce version particulière Jessaie de trouver un insulaire, Diffy, qui est soit plus lourd, soit plus léger que les 11 autres insulaires.

Leçons

La solution finale prend en compte deux choses que jai apprises tentatives précédentes:

1. Dans un groupe de quatre, je peux identifier Diffy en deux pesées.

   A. Dabord, jai placé deux insulaires du groupe contre deux connu non-Dif fys. Si la bascule sincline, je sais que Diffy est lun de ces deux. Si la bascule reste uniforme, je sais que Diffy est lun des deux autres.

   B. Maintenant, je sélectionne lun des deux Diffys possibles restants et le place contre un non-Diffy connu. Si léchelle sincline, jai trouvé Diffy. Si le plateau reste pair, je sais que Diffy est le dernier insulaire restant.

   C. Sinon, si la bascule sincline à létape A et que vous voulez savoir si DIffy est lourd ou léger, vous pouvez noter la direction de létape A et placer les deux Diffys possibles restants sur léchelle opposée. Si la bascule sincline dans la même direction que létape A, alors Diffy est celui qui est toujours du même côté que lors de létape A. Sinon, si lorientation de la bascule change, Diffy est de lautre côté.

2. Dans un groupe de trois, je peux identifier Diffy en une seule pesée, tant que jai des informations directionnelles. Je décrirai cela plus en détail sous Utilisation n ° 3.

Solution

À cause de la leçon n ° 1, je peux séparer quatre insulaires avant de vérifier le reste. Si Diffy est dans ce groupe de quatre, la première pesée sortira même, et je peux maintenant lidentifier parmi ces quatre avec mes deux mouvements restants. Si Diffy ne fait pas partie de ce groupe de quatre, jai maintenant quatre insulaires que je peux exclure et aussi utiliser pour tarer ma balançoire.

Donc, pour ma première utilisation de la balançoire, je pesez les huit insulaires restants les uns contre les autres avec quatre de chaque côté.

Utilisez # 1

Jai déjà décrit mon plan si cette première utilisation de la balançoire savère paire, alors quelle est la prochaine étape si cela savère étrange? Cest là que le génie entre en jeu.

Jai maintenant des « informations directionnelles ». Jappellerai désormais la direction de la bascule inclinée en utilisation 1 « Direction 1 » ou « D1 » pour faire court. Je sais que si Diffy est lourd, il est de la part de la balançoire qui est tombée, et si si Diffy est léger, il est de la part de la balançoire qui est montée. Si je déplace Diffy, la bascule changera dorientation! Il na pas le choix car Diffy, et seulement Diffy, fait basculer la bascule. Aussi, souvenez-vous de la leçon n ° 2, jai des informations directionnelles et un mouvement après lactuel, donc je peux totalement supprimer trois Diffys possibles avant la prochaine utilisation de la balançoire. Je vais devoir utiliser lun des insulaires que jai exclus dans lutilisation 1 afin de garder trois insulaires de chaque côté.

Utilisez # 2

Si Use # 2 nous donne une balançoire uniforme, nous pouvons trouver Diffy dans les trois que nous avons supprimés, mais si ce nest pas le cas, nous devons faire attention dans la direction dans laquelle se déplace la balançoire. At-il bougé de la même manière quavant, direction 1, ou a-t-il changé dorientation en direction 2? Notre prochain choix sera basé sur la réponse! Sil sest déplacé dans la direction 1, nous savons que Diffy nest pas lun des insulaires qui a changé de camp pour lutilisation n ° 2. Si la bascule se déplaçait dans la direction 2, alors Diffy est lun des sélecteurs latéraux. Quoi quil en soit, nous lavons réduit à être lun des trois ou deux. Lutilisation n ° 3 est un peu difficile à généraliser car elle est différente pour chaque possibilité.

Utilisation n ° 3

Dans le cas où jai un groupe de trois îlots Diffy possibles, deux de ces insulaires étaient du même côté pendant lutilisation n ° 1, lorsque la balançoire sest déplacée en D1. Si je mets un de ces insulaires de chaque côté de la balançoire et que la balançoire se déplace à nouveau en D1, alors nous savons que Diffy est lîlotier du côté dorigine. Si la bascule se déplace en D2, alors nous savons que Diffy est du côté opposé de la bascule. Si la bascule reste uniforme, nous savons que Diffy est le troisième membre du groupe.

Tout mappé

Commentaires

• Cette solution est imparfaite pour cette question.Ce nest acceptable que sils demandent didentifier Diffy mais pas sil est plus léger ou plus lourd (voir Paire – Paire – Même dans votre diagramme, L na pas été pondéré :)) Là encore, dans ce cas, nous pouvons résoudre le puzzle avec 13 personnes.

Ceci est une réécriture par R. Allen Gilliam de La solution de Jared Anderson à partir dune autre version de ce puzzle sur ce site. Cest peut-être comme ça que mon esprit fonctionne, mais cela semble beaucoup plus facile à comprendre.

Numérotez les hommes (ou pièces de monnaie ou balles) de 1 à 12.
Pesez 1 2 3 4 contre 5 6 7 8.
Sils sont identiques, alors lhomme différent est 9 10 11 ou 12. Passez à I ci-dessous.
Sils sont différents, notez si 1 2 3 4 est plus lourd ou plus léger.

Pesez 1 2 3 5 contre 4 10 11 12. (Notez que nous savons que 10 11 et 12 ne sont pas différents.) Il y a trois possibilités:
(1) Si 1235 a le même différence (plus lourde ou plus légère) que 1234, alors la différence doit être 1 2 ou 3 et a la même différence (plus lourde ou plus légère) que 1234. Passer à II ci-dessous.
(2) Si 1235 soldes 4 10 11 12 , alors le différent doit être 6 7 ou 8 (ceux que nous avons supprimés) et a la même différence (plus lourd ou plus léger) que 5678. Passer à II ci-dessous.
(3) Si 1235 a maintenant la différence opposée (plus lourd ou plus léger) comme 1234, alors 4 ou 5 est le différent. Soit 4 a la même différence que 1234 (plus lourd ou plus léger) ou 5 a la même différence que 5678 (plus lourd ou plus léger). Donc, nous pesons simplement 4 contre 1. Sils « sont identiques, alors 5 est le différent. Sils » sont différents, alors 4 est le différent.

I. Trouver lequel des 9 10 11 12 est différent avec deux pesées quand vous ne savez pas si le différent est plus lourd ou plus léger:

Pesez 9 contre 10. Deux possibilités:
(1) Si elles « sont différents, alors il faut que ce soit 9 ou 10. Pesez 9 et 11. Sils » sont identiques, 10 est le différent. Sils « sont différents, cest » 9.
(2) Sils « sont les mêmes, alors il doit être 11 ou 12. Pesez 9 et 11. Sils » sont identiques, 12 est le différent. Sils « sont différents, cest 11.
(Si cest » s 12, nous ne saurons pas sil était plus lourd ou plus léger puisque nous ne lavons jamais pesé. Nous lavons trouvé par élimination. Il doit être différent puisque tous les autres pèsent le même poids.)

II. Trouver lequel des trois hommes est différent en pesant un lorsque vous savez si le différent est plus lourd ou plus léger:

Renommez les trois hommes 1 2 3. Pesez 1 contre 2. Deux possibilités:
(1) Sils « sont identiques, 3 est le différent.
(2) Sils » sont différents, celui qui a la différence correcte rence (plus lourd ou plus léger) est le différent.

Cela semble être la solution la plus simple pour 12 objets si vous ne devez trouver que lobjet de poids différent, comme le demandent certaines versions du puzzle. La solution de Joe Z permet de trouver lélément et la différence avec 12 éléments, et lélément différent avec 13 éléments. Trouver lélément différent et la différence avec 14 éléments semble mathématiquement impossible avec 3 pesées car il ny a que 27 résultats possibles avec 3 pesées et il y a 28 possibilités avec 14 éléments. Mais une variante de la solution de Joe Z pourrait-elle trouver l’élément différent sur 13, et s’il est plus lourd ou plus léger? Si oui, alors trouver le différent mais pas la différence avec 14 Les articles seraient possibles. Trouver le différent mais pas la différence sur 15 serait impossible car vous ne pouvez laisser quun seul article de la pesée tout en étant capable didentifier le différent, et si vous pesez larticle, vous « ll savoir sil est plus léger ou plus lourd que nous savons mathématiquement impossible avec 14 éléments.

Cette solution est similaire à celui fourni par R Gilliam mais diffère dans la deuxième étape. Divi de les boules en 3 groupes de 4 boules chacun. Appelons-les g1 g2 et g3, choisissez deux groupes quelconques et comparez-les. Un des deux scénarios est vrai. Les casseroles sont équilibrées: les 8 balles que vous venez de peser ont toutes le poids correct. Les casseroles sont déséquilibrées: Le 4 balles que vous navez pas pesées ont toutes le poids correct.

Dans tous les cas, à la fin de la première pesée, vous avez au moins 4 balles du poids correct.

Pour la deuxième pesée un côté de la casserole doit avoir 3 boules du poids correct. Si les casseroles étaient déséquilibrées après la première pesée, mettez 3 balles de lune des casseroles déséquilibrées dans lautre casserole. Si les casseroles étaient équilibrées après la première pesée, mettez 3 des 4 boules qui ont posé la première pesée dans lautre plateau.

Si les casseroles sont déséquilibrées après cette pesée, vous saurez si la boule est plus lourde ou plus légère car lune des casseroles contient des boules du poids correct. Si les casseroles sont équilibrées, la 4 e balle qui a été laissée de côté est la balle étrange et vous pouvez savoir si elle est plus lourde ou li ghter en le pesant contre une balle de poids correct.

Si les casseroles sont déséquilibrées, vous savez si le bizarre est plus lourd ou plus léger. Prenez 2 des 3 balles du plateau (qui ne contient pas les bonnes balles de poids) et pesez-les lune contre lautre. Vous savez déjà si le bizarre est plus lourd ou plus léger. Si les casseroles ne sont pas équilibrées, choisissez la casserole qui correspond à la direction du poids de la boule. si les casseroles sont équilibrées, la 3ème balle est la boule.

Vous pouvez également la résoudre en utilisant 4 groupes de 3 balles . Pesez 3 contre 3 et si cela séquilibre, vous pouvez garder ces 6 balles de côté en tant quégaux connus. Sils ne séquilibrent pas, vous savez que la balle impaire est dans ce groupe de 6. Ensuite, pesez 3 des égalités connues contre lun des 2 groupes de 3 inconnues. Si elle équilibre, la balle impaire est en finale groupe de 3. Sil ne séquilibre pas, vous savez que limpair est toujours sur la balance. Enfin, en utilisant le dernier groupe de 3 balles inconnues et inégales, mettez-en une à chaque extrémité et gardez la troisième de côté. Si la balance est équilibrée, vous savez que la seule balle que vous avez gardée de côté est la balle impaire. Si l’échelle n’est pas équilibrée, vous savez que la balle impaire est sur l’échelle. Pour déterminer la balle impaire et si elle est plus lourde ou plus légère, vous devez avoir noté si le groupe inconnu était plus lourd ou plus léger que l’égalité connue. groupes. Sils étaient plus lourds, alors la balle solitaire est plus lourde.

Commentaires

•  » Pour déterminer le balle impaire et si elle ‘ est plus lourde ou plus légère, vous devez avoir noté si le groupe inconnu était plus lourd ou plus léger que les groupes connus-égaux.  » Si les trois groupes que vous avez pesés lors des deux premières pesées étaient égaux, alors vous navez ‘ pas cette information.

(1) Placez les boules 6 et 6 sur léchelle. Retirez-en un de chaque côté jusquà ce que la balance séquilibre.

(2) Prenez les deux dernières balles retirées (ou les deux restantes si la balance na jamais été équilibrée) et placez-les dun côté (côté A) et deux balles de poids égal de lautre (côté B). Si le côté A est plus bas, la balle bizarre est plus lourde, si la face B est inférieure, la balle bizarre est plus légère. Retirez-en un de chaque côté. Si léchelle est équilibrée, la balle retirée du côté A est la balle étrange, sinon la balle restante du côté A lest.

Commentaires

• Cela nécessite jusquà à sept pesées. Le problème vous demande de le faire en trois.
• @nosun – Bienvenue sur puzzling.se. Juste pour vous faire savoir, les réponses incorrectes sont parfois rejetées pour aider à les séparer des bonnes réponses. Cela ne vise pas à vous dissuader de fournir de bonnes réponses à d’autres questions.