Dvanáct koulí a stupnice

Rozdělte toto i n do tří skupin po čtyřech, A1, A2, A3, A4; B1, B2 …; C1, C2 … Každý krok zde odpovídá jednomu vážení.

• Zvažte A proti B.
  • Pokud A> B, pak zvažte A1, B1 a B2 proti B3 , B4 a C1.
    • Pokud jsou váhy stejné, pak jeden z A2 … 4 je těžší; vážit A2 a A3. Pokud jsou stejné, A4 je těžší. Pokud je jeden těžší, pak je ten míč nejtěžší.
    • Pokud je první skupina těžší, pak je buď A1 těžší, nebo B3-4 je lehčí. Porovnejte B3 a B4; pokud jsou stejné, A1 je těžší; pokud se liší, nejsvětlejší je nejsvětlejší koule.
    • Pokud je první skupina světlejší, pak je světlejší buď B1 nebo B2. Zvažte je a uvidíte.
  • Pokud A < B, přečíslujte všechny A-koule na B-koule a proveďte výše uvedené kroky.
  • Pokud A = B, zvažte A1, A2, A3 proti C1, C2, C3
    • Pokud jsou stejné, zvažte A1 proti C4. Pokud je A1 lehčí, pak C4 je lichá koule a je těžká. Pokud je A1 těžší, pak C4 je lichá koule a je lehká.
    • Pokud je A těžší než C, zvažte C1 proti C2. Pokud jsou stejné, pak C3 je lichá koule a je světlejší. Pokud nejsou stejné, pak je lehčí ze dvou koulí nejsvětlejší koulí.
    • Pokud je A lehčí než C, zvažte C1 proti C2. Pokud jsou stejné, pak C3 je lichá koule a je těžší. Pokud nejsou stejné, pak je těžší ze dvou míčků nejtěžší míč.

Můžeme pracovat zpětně od třetím krokem je přibližně zjistit, proč to funguje. Při třetím vážení je třeba možnosti omezit na dvě nebo tři koule. To znamená, že druhé vážení se musí snížit na dvě nebo tři možné kuličky.

Víme, že první krok odstraní 1/3 nebo 2/3 možných řešení, bez ohledu na to, co děláte. To znamená, že v případě 1/3 musíte rozdělit možnosti dolů z 8 na skupinu 3, skupinu 3 a skupinu 2. Z toho třetí vážení ukazuje na lichý míč ven. Protože z tohoto případu vyplývá, že jedna sada koulí je těžší, na základě nalezení liché koule ven víme, zda je „těžší nebo lehčí, takže si s touto informací nemusíme vůbec dělat starosti.

V případě 2/3 musíte omezit možnosti na skupinu 3 a skupinu 1, což je intuitivní. Protože v tomto případě vlastně neznáme relativní váhu liché koule, je nutné k určení, zda je koule těžší nebo lehčí, použít informace ze třetího vážení.

Komentáře

• I když je tato odpověď správná, doufal jsem v odpověď, která by vysvětlila strategii, která stojí za výběrem položek, které je třeba zvážit.
• @JoeZ. I ‚ Přidal jsem trochu o tom, jak jsem určil tuto odpověď, i když si ‚ nejsem jistý, že mohu mluvit o obecném řešení tohoto problému. (Také Pro vaši informaci, ‚ jsem upravil svou odpověď na vaši další otázku.)
• Co jste ‚ dal fajn. Přemýšlel jsem o uvažování víc než o strategii, přemýšlej o tom znovu.

Tady je další způsob, jak tento problém vyřešit, který vůbec nezahrnuje žádné podmíněné větvení. Ve skutečnosti je možné předem nastavit pevný plán vážení a stále určit, která koule je lehčí nebo těžší, pouze za 3 vážení. „Níže vysvětlím, jak níže.

Podstatou takových problémů je, kolik informací můžete získat z postupu, který jste mohli provést? Při každém vážení se váha může naklonit doleva, doprava nebo zůstat vyvážená.Získáte tak celkem 3 ³ = 27 možných výsledků a v tomto případě z nich musíte rozlišit 24 výsledků (jeden z 12 míčů je lehký nebo těžký, což je 12 × 2 = 24 ).

Takže musíme zahájit zdlouhavý úkol mapovat každý výsledek na výsledek.

Jednou z věcí, které si okamžitě všimneme, je, že každý míč má také tři stavy může být během každého vážení – na levé straně váhy, na pravé straně váhy nebo mimo váhu. Přirozeně se to mapuje na stavy stupnice způsobem, který je intuitivně analogický:

Pokud je lichý míč ven těžší …

• a míč je umístěna na levé straně, stupnice se nakloní doleva.
• a míč se umístí na pravou stranu, stupnice se nakloní doprava.
• a míč mimo stupnici zůstane stupnice vyvážená.

Pokud je míč světlejší, první dva případy jsou obrácené.

Existuje 27 možných způsobů umístění každého míčku ve všech třech váženích, z nichž každé odpovídá jinému výsledku, pokud je ta koule lichá. Musíme najít uspořádání koulí, kde je každá možná sada umístění a její inverze (pro těžké a lehké případy) odlišná – takže ne dvě koule jsou na stejném místě pro všechna tři vážení.

Toto je předběžné uspořádání, které splňuje vlastnost odlišnosti. Všimněte si, že v obou tabulkách se žádné možné uspořádání neobjeví více než jednou:

 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 

Okamžitě narazíme na problém, že nedáváme stejný počet koule na každé stupnici. Pokud máte sedm míčků na jedné straně a jednu na druhé, samozřejmě se váha nakloní na stranu se sedmi míčky (pokud váš podivný míč není směšně těžký, ale nebavte se, že scénář). Musíme tedy převrátit několik z těchto konfigurací, abychom pro každé vážení dávali na každou stranu čtyři. U některých pokusů a omylů můžeme získat něco takového:

 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 

Náš konečný plán vážení kuliček je tedy následující:

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 

A výsledky jsou interpretovány takto:

==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 

A tak jsme vytvořili schéma vážení, kde je každé vážení předem předem předem určeno, které stále dokáže určit, která koule je ta lichá, a zda je lehčí nebo těžší.

Můžete si všimnout, že jsme nepoužili LLL, RRR nebo === v našich dohodách.

Nemůžeme použít LLL a RRR jako 13. pár pro 13. míč, protože pak bychom nakonec museli umístit devět míčků na váhu, a není možné to udělat, protože devět je liché. pravděpodobně by to mohl použít v místo jednoho z LLR/RRL párů, ale ponechání LLL a RRR out vytváří ve výsledkové tabulce symetrii, která se mi spíše líbí.

Zajímavé však je, že můžete mít 13. míč, který nikdy Umístěte je na libovolné stupnici a pokud se vaše váhy vyrovnají ve všech třech váženích, třináctý míč, který jste nikdy nevážili, je tím zvláštním míčem (i když očividně to bez čtvrtého vážení nezjistíte, zda je lehčí nebo těžší).

Komentáře

• Takže v zásadě to lze vyřešit pomocí 13 míčů, pokud má 14. míč etalon. Skvělá odpověď.
• Pravděpodobně i 14 míčků, kde 14. míč může být těžší, je řešitelný, ale je to těžší, s největší pravděpodobností ‚ t.

Některé ze stávajících odpovědí na tuto starodávnou otázku jsou vynikající, ale existuje jedna slavná odpověď, že Myslím, že si zde zaslouží zmínku. Vychází z článku v Eureka , každoročním časopise studentské matematické společnosti University of Cambridge, který napsal CAB Smith pod pseudonymem „Blanche Descartes“.

Má dvě velmi pěkné funkce. První je, že jde o „nerozvětvené“ řešení: nemusíte měnit to, co děláte při pozdějších váženích, v závislosti na výsledcích předchozích. Druhým je to, že jakmile to „uvidíte“, je téměř nemožné zapomenout.

Smithovo řešení je napsáno zcela ve verši a obsahuje vysvětlení, jak to celé funguje, ale já uvedu pouze skutečná odpověď. „F“ zde je náš protagonista profesor Felix Fiddlesticks, jehož matka ho požádala o pomoc s hlavolamem. Provedl jsem několik drobných změn v původním formátování.

F vyloží mince v řadě
A na každé křídou nakreslete písmeno, takže,
Chcete-li vytvořit slova: F AM NOT LICKED
(An myšlenka v jeho mozku klikla.)

A teď jeho matka „přikazuje:
“ MA, DO / LIKE
ME TO / FIND
FAKE / COIN! „

Každý ze tří řádků příkazu F popisuje jedno vážení.Když jste je všechny provedli, výsledky jednoznačně určí, která mince je falešná a jakým způsobem.

Komentáře

• +1. je zkrášlená verze Joe Z ‚ s odpovědí

Strávil jsem nějaký čas prací na této skládačce poté, co se objevila na „Brooklyn Nine-Nine“ (pokud chcete, můžete sledovat, jak kapitán Holt popisuje skládačku zde ) a zde jsem napsal podrobné ilustrované řešení: Řešení pro řešení ostrovů v Tyreses . V tomto konkrétní verze Pokouším se najít ostrovana Diffyho, který je buď těžší, nebo lehčí než ostatních 11 ostrovanů.

Lekce

Konečné řešení zohledňuje dvě věci, z nichž jsem se poučil předchozí pokusy:

1. Ve skupině čtyř mohu identifikovat Diffyho ve dvou váženích.

   A. Nejprve jsem nastavil dva ostrovany ze skupiny proti dvěma známý non-Dif fys. Pokud se houpačka nakloní, vím, že Diffy je jedním z těchto dvou. Pokud houpačka zůstane sudá, vím, že Diffy je jedním z dalších dvou.

   B. Nyní jsem vybral jednoho ze zbývajících dvou možných – Diffys a postavil ho proti známému non-Diffymu. Pokud se váha nakloní, našel jsem Diffyho. Pokud deska zůstane vyrovnaná, vím, že Diffy je posledním zbývajícím ostrovanem.

   C. Alternativně, pokud se houpačka v kroku A nakloní a chcete vědět, zda je DIffy těžký nebo lehký, můžete si všimnout směru z kroku A a umístit dva zbývající možné – Diffy na stupnici proti sobě. Pokud se houpačka nakloní ve stejném směru jako krok A, pak je Diffy stále na stejné straně jako v kroku A. Jinak, pokud se změní orientace houpačky, je Diffy na druhé straně.

2. Ve skupině tří můžu identifikovat Diffy v jednom vážení, pokud mám informace o směru. Popíšu to podrobněji v části Použití č. 3.

Řešení

Kvůli lekci č. 1 mohu před kontrolou ostatních rozdělit čtyři ostrovany. Pokud je Diffy v této skupině čtyř, první vážení vyjde dokonce, a já ho nyní mohu identifikovat z těch čtyř pomocí svých dvou zbývajících tahů. Pokud Diffy není v této skupině čtyř, mám nyní čtyři ostrovany, které mohu vyloučit a také je použít k tárování mé houpačky.

Takže při mém prvním použití houpačky jsem zvážte osm zbývajících ostrovanů proti sobě se čtyřmi na každé straně.

Použijte # 1

Už jsem nastínil svůj plán, pokud se toto první použití houpačky ukáže jako sudé, tak co dál, když se to ukáže divné? Tady přichází genialita.

Nyní mám nějaké „směrové informace“. Od nynějška zavolám kterýmkoli směrem, kterým se houpačka naklonila v Použití 1, „Směr 1“ nebo „D1“. Vím, že pokud je Diffy těžký, je na straně houpačky, která šla dolů, a pokud je Diffy lehký, je na straně houpačky, která šla nahoru. Pokud pohnu Diffy, houpačka změní orientaci! Nemá na výběr, protože Diffy a pouze Diffy způsobí naklonění houpačky. Nezapomeňte také na lekci č. 2, mám směrové informace a jeden pohyb po aktuálním, takže mohu před dalším použitím houpačky úplně vyjmout tři možné Diffys. Budu muset použít jednoho z ostrovanů, které jsem v Použití 1 vyloučil, aby na každé straně zůstaly tři ostrované.

Použijte # 2

Pokud nám použití # 2 dává rovnoměrnou houpačku, najdeme Diffy ve třech, které jsme odstranili, ale pokud ne, musíme věnovat pozornost do směru, kterým se houpačka pohybuje. Pohybovalo se to stejným způsobem jako předtím, směr 1, nebo se změnila orientace na směr 2? Naše další volba bude založena na odpovědi! Pokud by se pohyboval ve směru 1, pak víme, že Diffy není jedním z ostrovanů, kteří změnili stranu pro použití # 2. Pokud se houpačka pohnula ve směru 2, pak je Diffy jedním z bočních přepínačů. Ať tak či onak, dostali jsme ho k tomu, aby byl jedním ze tří nebo dvou. Použití # 3 je trochu těžké zobecnit, protože pro každou možnost je jiné.

Použití # 3

V případě, že mám skupinu tří možných ostrovanů Diffy, dva těchto ostrovanů bylo na stejné straně během použití č. 1, kdy se houpačka přesunula do D1. Pokud položím jednoho z těchto ostrovanů na každou stranu houpačky a houpačka se znovu přesune do D1, pak víme, že Diffy je ostrovan na původní straně. Pokud se houpačka přesune do D2, pak víme, že Diffy je na opačné straně houpačky. Pokud houpačka zůstane rovnoměrná, víme, že Diffy je třetím členem skupiny.

All Mapped Out

Komentáře

• Toto řešení má u této otázky chybu.Je přijatelné pouze v případě, že požádají o identifikaci Diffyho, ale ne o to, zda je lehčí nebo těžší (viz Sudé – Sudé – I ve vašem diagramu L nebylo váženo :)) Pak znovu, v tom případě můžeme vyřešit hádanku s 13 lidé.

Toto přepisuje R. Allen Gilliam z Řešení Jared Anderson z jiné verze této hádanky na tomto webu. Možná je to způsob, jakým funguje moje mysl, ale zdá se, že je mnohem snazší pochopit.

Počet mužů (nebo mincí nebo koulí) 1 až 12.
Zvažte 1 2 3 4 proti 5 6 7 8.
Pokud jsou stejní, pak je jiný muž 9 10 11 nebo 12. Přejít na I níže.
Pokud se liší, poznamenejte si, zda je 1 2 3 4 těžší nebo lehčí.

Zvažte 1 2 3 5 proti 4 10 11 12. (Všimněte si, že víme, že 10 11 a 12 nejsou odlišné.) Existují tři možnosti:
(1) Pokud má 1235 stejný rozdíl (těžší nebo lehčí) jako 1234, pak rozdíl musí být 1 2 nebo 3 a má stejný rozdíl (těžší nebo lehčí) jako 1234. Přejít na II níže.
(2) Pokud 1235 zůstatky 4 10 11 12 , pak jiný musí být 6 7 nebo 8 (ty, které jsme odstranili) a má stejný rozdíl (těžší nebo lehčí) jako 5678. Přeskočit na II níže.
(3) Pokud má nyní 1235 opačný rozdíl (těžší nebo lehčí) jako 1234, pak 4 nebo 5 je jiný. Buď 4 má stejný rozdíl jako 1234 (těžší nebo lehčí), nebo 5 má stejný rozdíl jako 5678 (těžší nebo lehčí). Takže jednoduše vážíme 4 proti 1. Pokud jsou stejné, pak 5 je jiné. Pokud jsou jiné, pak 4 je jiné.

I. Zjištění, které z 9 10 11 12 se liší dvěma váženími, když nevíte, zda je jiné těžší nebo lehčí:

Zvažte 9 proti 10. Dvě možnosti:
(1) Pokud „Jsou jiní, pak to musí být 9 nebo 10. Vážit 9 a 11. Pokud jsou stejní, 10 je odlišných. Pokud jsou odlišní, je to 9.
(2) Pokud „Jsou stejné, pak to musí být 11 nebo 12. Váha 9 a 11. Pokud jsou stejné, 12 je jiné. Pokud jsou jiné, je to 11.
(Pokud ano“ S 12, nebudeme vědět, zda byl těžší nebo lehčí, protože jsme ho nikdy nevážili. Našli jsme ho procesem eliminace. Musí to být jiný, protože všechny ostatní váží stejně.)

II. Zjištění, který ze tří mužů se liší od jednoho vážení, když víte, zda je ten jiný těžší nebo lehčí:

Přejmenujte tři muže 1 2 3. Zvažte 1 proti 2. Dvě možnosti:
(1) Jsou-li stejné, 3 jsou odlišné.
(2) Jsou-li různé, podle toho, který z nich má správný rozdíl rence (těžší nebo lehčí) je jiný.

Toto se jeví jako nejjednodušší řešení pro 12 položek, pokud musíte najít pouze předmět s různou hmotností, jak požadují některé verze skládačky. Řešení Joe Z může najít položku a rozdíl s 12 položkami a jinou položku s 13 položkami. Hledání jiné položky a rozdílu se 14 položkami se zdá matematicky nemožné u 3 vážení, protože při 3 váženích je pouze 27 možných výsledků a existuje 28 možností se 14 položkami. Mohla by však varianta řešení Joe Z najít jinou položku ze 13 a zda by byla těžší nebo lehčí? Pokud ano, pak najít jinou, ale ne rozdíl s 14 Bylo by možné najít jiný, ale ne rozdíl z 15, protože z vážení můžete ponechat pouze jednu položku, přičemž stále můžete identifikovat jinou položku, a pokud vážíte položku, budete vědět, zda je to u 14 položek lehčí nebo těžší, o kterém víme, že je matematicky nemožné.

Toto řešení je podobné ten, který poskytl R Gilliam, ale liší se ve druhém kroku. Divi de koule do 3 skupin po 4 koulích každý. Pojďme je nazvat g1 g2 a g3, vybrat si libovolné dvě skupiny a zvážit je proti sobě. Jeden ze dvou scénářů je pravdivý. Pánve jsou vyvážené: 8 míčků, které jste právě odvážili, má správnou hmotnost. Pánev je nevyvážená: 4 kuličky, které jste nevážili, mají správnou hmotnost.

Ať tak či onak, na konci prvního vážení máte alespoň 4 kuličky se správnou hmotností.

Pro druhé vážení jedna strana pánve by měla mít 3 kuličky správné hmotnosti. Pokud byly misky po prvním vážení nevyvážené, vložte do druhé misky 3 kuličky z jedné z nevyvážených misek. Pokud byly misky po prvním vážení vyvážené, položte 3 misky 4 míčky, které odložily první vážení do druhé misky.

Pokud jsou misky po tomto vážení nevyvážené, budete vědět, zda je oddball těžší nebo lehčí, protože jedna z misek obsahuje koule správné hmotnosti. Pokud jsou pánve vyvážené, 4. míč, který byl vynechán, je podivín a můžete zjistit, zda je těžší nebo li vážením proti kuličce správné hmotnosti.

Pokud jsou pánve nevyvážené, víte, zda je oddball těžší nebo lehčí. Vezměte 2 ze 3 koulí z pánve (která neobsahuje správné kuličky) a zvažte je proti sobě. Už víte, zda je oddball těžší nebo lehčí. Pokud jsou pánve nevyvážené, vyberte misku, která odpovídá směru hmotnosti oddball. pokud jsou pánve vyvážené, 3. míč je zvláštní míč.

Můžete to také vyřešit pomocí 4 skupin po 3 míčích . Zvažte 3 proti 3 a pokud se to vyrovná, můžete si těch 6 míčků ponechat stranou jako známé-rovné. Pokud nevyrovnají, víte, že lichý míč je v této skupině 6. Dále zvažte 3 ze známých – rovná se proti kterékoli ze 2 skupin po 3 neznámých. Pokud to vyváží, lichý je ve finále skupina 3. Pokud to není v rovnováze, víte, že ten zvláštní je stále na stupnici. Nakonec použijte poslední skupinu 3 míčků, která je neznámá a nerovná, jednu na každý konec a třetí stranou. Pokud se váha vyrovná, víte, že osamělá koule, kterou jste drželi stranou, je lichá koule. Pokud váha nevyvažuje, víte, že na ní je lichá koule. Chcete-li určit lichou kouli a zjistit, zda je těžší nebo lehčí, musíte si všimnout, zda neznámá skupina byla těžší nebo lehčí než známá-stejná skupiny. Pokud byly těžší, pak je osamělá koule těžší.

Komentáře

• “ Určení lichý míč a zda je ‚ těžší nebo lehčí, musíte si všimnout, zda neznámá skupina byla těžší nebo lehčí než skupiny známé-stejné. “ Pokud byly všechny tři skupiny, které jste vážili v prvních dvou váženích, stejné, pak tyto informace nemáte ‚.

(1) Umístěte míčky 6 a 6 na váhu. Odstraňte jednu z každé strany, dokud se váha nevyrovná.

(2) Vezměte poslední dva odstraněné (nebo zbývající dva, pokud měřítko nikdy není vyvážené) a umístěte je na jednu stranu (strana A) a dvě stejně vážené koule na druhou (strana B). Pokud je strana A nižší, oddball je těžší, pokud je strana B nižší, oddball je světlejší. Odstraňte jednu z každé strany. Pokud se váha vyrovná, míč odebraný ze strany A je podivín, pokud ne míč zbývající ze strany A je.

Komentáře

• To vyžaduje až až sedm vážení. Problém vás požádá, abyste to provedli ve třech.
• @nosun – Vítejte na stránce puzzling.se. Chceme vás informovat, že nesprávné odpovědi se někdy odmítnou hlasovat, aby se mohly oddělit od dobrých odpovědí. To vás nemá odradit od poskytování dobrých odpovědí na další otázky.