Onze recente reeks puzzels kenmerkte de eenvoudige weegschaal met twee pannen, historisch gezien een symbool van handel en overheid, kunst en wetenschap. Evenwichtsschalen zijn ook populair in recreatieve wiskunde. Evenwichtspuzzels vereisen een duidelijke, logische redenering en lenen zich goed voor wiskundige generalisatie. Laten we eens kijken hoe Quanta lezers brachten deze kwaliteiten in evenwicht in de onderstaande puzzels.
Puzzel 1
Je hebt acht identiek ogende munten. De ene is namaak en lichter dan de andere, die hetzelfde gewicht hebben. Vind de slechte munt in twee wegingen. Zoek de algemene formule voor het maximale aantal munten waarvan u de valse kunt vinden in x wegingen.
Het aanpakken van een eenvoudige versie van een probleem onthult vaak de sleutel tot de oplossing. Stel je in dit geval voor dat je slechts drie munten hebt, waarvan er één lichter is dan de andere twee. Als je een van hen afweegt tegen een van de andere twee, zullen ze in evenwicht zijn of niet. Als ze dat niet doen, weet je wat lichter is. Als ze wel in evenwicht zijn, dan is de derde de lichte. U heeft slechts één weging nodig.
Dus als je in deze puzzel een groep van drie (of minder) kunt isoleren die de lichte munt bevatten bij de eerste weging, heb je nog één weging nodig. U kunt dit doen door elke drie tegen elke andere drie te balanceren. Als de twee groepen niet in balans zijn, hebt u de groep met de lichte gevonden en kunt u doorgaan zoals hierboven beschreven voor de tweede weging. Als ze in evenwicht zijn, weeg dan gewoon de resterende twee munten tegen elkaar en je zult de lichte vinden.
Merk op dat dit ook werkt als er drie in de ongewogen groep zitten, dus we hadden met negen munten kunnen beginnen. Door deze logica te volgen en te beginnen met drie munten, kunnen we voor elke extra weging de lichte munt vinden in drie keer het aantal munten dat we eerder hadden. De formule die ons het maximale aantal munten geeft n in w wegingen is dus n = 3w.
Puzzel 2
Je hebt 12 identiek ogende munten. De ene is zwaarder of lichter dan de andere, die identieke gewichten hebben.
-
Vind de slechte munt in drie wegingen.
-
Wat is het maximale aantal munten waarvan je op vier wegingen de slechte kunt vinden? Beschrijf hoe u de valse munt zou vinden.
De oplossing van deze puzzel werd goed beschreven door Ted, die ook liet zien dat je de slechte munt tussen 13 munten in drie wegingen kunt detecteren. Hier is de oplossing van Ted (met inkepingen om de drie wegingen in elk geval te scheiden):
Begin met het wegen van 4 munten versus 4 munten.
Geval 1: Indien onevenwichtig, plaats voor de tweede weging 2 van elk van de zwaardere zijde aan beide zijden van de weegschaal, samen met 1 van elk van de lichtere zijde.
1a: Indien onevenwichtig, is de slechte munt ofwel de 2 munten die nog steeds aan de zware kant zijn of de enkele munt die nog steeds aan de lichte kant is.
Weeg de 2 mogelijk zware munten, de slechte is ofwel de zwaardere van de twee, of de enkele lichte als ze in evenwicht zijn.
1b: Als de tweede weging in evenwicht is, is de slechte munt een van de 2 ongebruikte munten van de lichtere kant van de eerste weging.
Weeg ze tegen elkaar af, de lichtere is slecht.
Geval 2: Indien gebalanceerd, is de slechte munt een van de 5 overgebleven. Weeg er 3 af tegen de 3 die al gewogen zijn (waarvan bekend is dat ze goed zijn).
Geval 2a: Als de munt uit balans is, weet je dat de slechte munt een van die 3 is en of hij licht of zwaar is.
De derde weging is elke 2 van die tegen elkaar - als het onevenwichtig is, identificeert dat de slechte munt, als het in evenwicht is, is het de laatste van de drie.
Geval 2b: Als de tweede weging in evenwicht is, is de slechte munt een van de resterende 2.
Weeg een van beide tegen een bekende goede munt. Als dit resultaat onevenwichtig is, is deze nieuwe munt slecht en weet je of hij zwaar of licht is. Als dit resultaat in evenwicht is, is de 13e munt slecht, maar het is niet bekend of deze zwaar of licht is (wat we niet hoeven te weten, dus we zijn klaar).
Ted liet ook zien dat het maximale aantal munten voor vier wegingen 40 is. De formule voor deze puzzel is: n = (3w − 1)/2.
Voor de resterende puzzels worden de algemene formules nog steeds onderzocht door professionele wiskundigen en zijn ze het onderwerp van gepubliceerde artikelen, waarvan sommige zijn geciteerd door Rainer uit de lente. Ik zal me beperken tot oplossingen voor de kleine aantallen munten die we in de puzzels beschouwen en zal alleen generalisaties noemen die op natuurlijke wijze volgen uit de methoden die in deze gevallen worden gebruikt.
Puzzel 3
Dit is een variatie op puzzel 1. Je hebt weer acht identiek ogende munten, waarvan er één lichter is dan de andere. Nu heb je echter drie schalen. Twee van de schalen werken, maar de derde is kapot en geeft willekeurige resultaten (soms is het goed en soms fout). Je weet niet welke schaal kapot is. Hoeveel wegingen zijn er nodig om de lichte munt te vinden?
Zoals we in probleem 1 zagen, zijn er slechts twee wegingen nodig met een goede balans. We weten ook dat de twee goede balansen het altijd eens zullen zijn, dus als we elke weging op alle drie de balansen herhalen, zullen we het antwoord in zes wegingen hebben, zoals een lezer suggereerde. Als we het in een kleiner aantal wegingen proberen te doen, wordt het een beetje lastig. We kunnen geen goede weegschaal identificeren door dezelfde munten op twee weegschalen te wegen, want zelfs als ze overeenkomen, kan een van de twee nog steeds een slechte weegschaal zijn. (Dit laat ook zien hoe gemakkelijk desinformatie of willekeurige informatie de waarheid kan verdoezelen.)
Sterker nog, dit probleem is heel slim op te lossen in slechts vier wegingen! Rainer uit de lente plaatste de oplossing met een nieuwerwetse notatie die voor deze puzzel lijkt te zijn gemaakt. Maar voordat je daarheen gaat, wil ik dat je je een scenario voorstelt waarvan ik hoop dat het de dingen intuïtiever maakt.
Stel je voor dat je een rechercheur bent die onderzoek doet naar een vluchtmisdrijf in een klein land waarvan de auto's tweecijferige kentekenplaten hebben met alleen de cijfers 0, 1 en 2. Drie mensen, A, B en C, hebben het incident waargenomen. Twee van hen beantwoorden een driekeuzevraag altijd correct en één geeft volledig willekeurige antwoorden. Je weet niet wie de willekeurige antwoorder is. Je moet elk van hen een enkele vraag met drie keuzes stellen en vervolgens degene kiezen die absoluut de waarheid vertelt om meer informatie te krijgen.
Hier is hoe je het doet. Vraag A of het eerste cijfer 0, 1 of 2 is. Laten we zeggen A zegt 2. Vraag B of het tweede cijfer 0, 1 of 2 is. Laten we zeggen B zegt 1. Vraag C dan om een keuze te maken tussen deze drie uitspraken:
- Alleen A spreekt de waarheid.
- Alleen B spreekt de waarheid.
- Beiden spreken de waarheid.
U kunt degene geloven die C u zegt en die persoon ondervragen over het andere cijfer. Om te zien waarom, bedenk dat als A liegt, C betrouwbaar is en zal zeggen dat B de waarheid spreekt. Het tweede cijfer wordt dan namelijk een 1 en je kunt dan vraag B stellen over het eerste cijfer. Evenzo, als B liegt, dan is C weer betrouwbaar en zal hij zeggen dat A de waarheid spreekt. Dan is het eerste cijfer in feite 2 en kun je vraag A stellen over het tweede cijfer. Tot slot, als C liegt, dan zijn zowel A als B betrouwbaar, dus je kunt nog steeds geloven en kiezen wie C zegt. (En als C zegt dat zowel A als B de waarheid vertellen, dan moeten ze dat allebei zijn.) De sleutel hier is dat je keuze van vragen C niet toelaat om op een zodanige manier te liegen dat er twijfel ontstaat over zowel A als B. Aangezien ten minste één van A en B betrouwbaar moet zijn, kun je altijd degene kiezen waarmee C het eens is, ook al is het maar een willekeurig antwoord. Als ze het alle drie eens zijn, dan heb je al beide cijfers van het kenteken.
Hier leest u hoe u dit verhaal terugvertaalt naar onze puzzel. De schalen zijn A, B en C. U kunt de twee cijfers van de kentekenplaat als volgt naar de munten vertalen: 01 is munt 1, 02 is munt 2, 10 is munt 3, 11 is munt 4, 12 is munt 5, 20 is munt 6, 21 is munt 7 en 22 is munt 8. Oplettende lezers zullen herkennen dat dit het basis 3 (of ternaire) getalsysteem is. Merk ook op dat er een extra mogelijk nummer 00 is, dat u kunt gebruiken voor een negende munt waarvoor deze techniek ook zal werken, zoals in puzzel 1.
Voor de eerste weging deelt u de munten door hun eerste (basis 3) cijfer, dus uw drie groepen zijn munten [1, 2], [3, 4, 5] en [6, 7, 8]. Weeg [3, 4, 5] tegen [6, 7, 8] op schaal A. Als A goed werkt, heb je de juiste eerste cijfergroep zoals in puzzel 1. Evenzo geldt voor de tweede weging op schaal B je groepen zijn die met hetzelfde tweede cijfer: [1, 4, 7], [2, 5, 8] en [3, 6]. Als B goed werkt, heb je het juiste tweede cijfer. Voor de derde weging, op schaal C, weeg je de groep die A identificeerde tegen de groep die B deed. In navolging van ons voorbeeld zijn de groepen voor 21 [6, 7, 8] en [1, 4, 7]. Munt 7 kan niet aan beide kanten tegelijk worden geplaatst, dus laten we deze weg en wegen [6, 8] en [1, 4] tegen elkaar af. Merk op dat als A en B beide betrouwbaar zijn, 7 in feite het juiste antwoord is, en het maakt niet uit welke kant er lichter uitkomt op C. Als de weging op C toevallig in evenwicht is, dan zijn alle drie de schalen het eens, en je hebt je antwoord (muntstuk 7) in slechts drie wegingen. Als A betrouwbaar is en B niet, bevindt de lichtere munt zich in [6, 8], welke schaal C zal bevestigen, en als B betrouwbaar is en A niet, bevindt de lichtere munt zich in [1, 4], welke schaal C zal ook bevestigen.
Dus in drie wegingen hebben we ofwel de lichte munt geïdentificeerd of teruggebracht tot een groep van twee, en we hebben ook een werkende weegschaal geïdentificeerd. De vierde weging op schaal A of schaal B (welke schaal C ook heeft afgesproken) doet de rest.
Deze oplossing lijkt me waanzinnig mooi!
Deze methode kan worden gegeneraliseerd om de lichte munt onder 3 te vinden2x munten in 3x + 1 weging met de meegeleverde weegschaal. U heeft dus zeven wegingen nodig voor 81 munten. Voor grotere aantallen munten (>~1,000) een nog sterkere oplossing bestaat.
Puzzel 4
Je hebt 16 munten, waarvan acht zwaar en van hetzelfde gewicht. De andere acht zijn licht en van hetzelfde gewicht. Je weet niet welke munten zwaar of licht zijn. De munten zien er identiek uit, behalve één met speciale markeringen. Kun je met één goede weegschaal bepalen of de speciale munt in drie wegingen licht of zwaar is? Wat is het maximale aantal munten waarmee je kunt beginnen en dit probleem succesvol kunt oplossen in vier wegingen?
Op het eerste gezicht lijkt deze puzzel bijna onmogelijk om in drie wegingen te doen, concludeerde een van onze lezers. Desalniettemin kan het met enige slimheid worden gedaan, en beide Ted en Rainer uit de lente juiste oplossingen gegeven. Ted gaf enkele onschatbare algemene principes die de moeite waard zijn om op te letten.
Ten eerste, totdat u een onevenwichtig resultaat krijgt van een weging, heeft u niet genoeg informatie om te bepalen of de speciale munt zwaar of licht is. Je moet dus proberen een onevenwichtig resultaat te forceren.
Ten tweede, als je een gebalanceerd resultaat krijgt (bijvoorbeeld de speciale munt A brengt munt B in evenwicht), kun je de munten die in evenwicht zijn combineren en ze wegen tegen nog twee munten, C en D. Als ze uit balans zijn, heb je het antwoord; anders heb je nu het aantal vergelijkbare munten verdubbeld, wat je zou kunnen helpen om een onevenwichtig antwoord te krijgen bij de volgende weging. U kunt dit proces ook omgekeerd uitvoeren met aantallen munten die machten van twee zijn (4, 8, enz.) als u een aanvankelijk onevenwichtig resultaat heeft, zoals te zien is in de volgende oplossing.
Hieronder staat de gehele procedure die in alle gevallen in drie wegingen het type van de bijzondere munt A kan identificeren. (B, C en D zijn drie munten die aan dezelfde kant als A zijn geplaatst bij een gewicht van 1 (W1); X en Y zijn de twee munten die niet worden gebruikt in W1.)
Deze puzzel is bedacht door de Russische wiskundige Konstantin Knop, een wereldautoriteit op het gebied van puzzels met het wegen van munten. Veel van zijn papieren zijn in het Russisch, maar je kunt verschillende muntpuzzels vinden (naast andere interessante puzzels) op de blog van zijn medewerker Tanya Khovanova.
Wat de generalisatie betreft, laat ik het aan jou over om te zien of dezelfde methode werkt om het type van een speciale munt te vinden tussen 32 munten, waarvan 16 zware en 16 lichte.
Puzzel 5
U heeft n identiek ogende munten, waarvan sommige vals en lichter zijn dan andere. Het enige wat je weet is dat er minstens één valse munt is en dat er meer normale munten zijn dan valse. Jouw taak is om alle valse munten te detecteren.
Het feit dat er minstens één lichte munt is en dat er meer normale munten zijn dan lichte, maakt deze puzzel minder complex dan hij op het eerste gezicht lijkt, althans voor kleine aantallen. Laten we eens kijken naar het aantal wegingen van één tot acht munten.
Voor één en twee munten kunnen er geen lichte munten zijn volgens de tweede voorwaarde, dus er zijn geen wegingen vereist.
Drie munten: slechts één lichte munt. Eén weging nodig per puzzel 1.
Vier munten: slechts één lichte munt. Een extra weging nodig, dus w = 2.
Vijf munten: één tot twee lichte munten. Dit is het eerste interessante geval. De vraag is: moeten we één munt tegen één wegen, of twee munten tegen twee?
Als we één tegen één afwegen, kunnen we hebben:
- Twee ongebalanceerde wegingen: twee munten ontdekt; we zijn klaar.
- Eén uitgebalanceerde weging van twee: de uitgebalanceerde munten moeten normaal zijn, dus de laatste munt moet opnieuw worden gewogen, w = 3.
- Twee gebalanceerde wegingen: Weeg bij de derde weging één munt van elke voorgaande weging tegen een andere. Als ze in evenwicht zijn, zijn ze alle vier normaal en is munt 5 de lichte. We zijn klaar; w = 3 weer. Als ze uit balans zijn, hebben we de twee lichte munten gevonden en zijn we na drie wegingen klaar.
Als we in plaats daarvan twee tegen twee wegen, hebben we nog steeds drie wegingen nodig, omdat we onderscheid moeten maken tussen de mogelijkheden dat de munten aan beide kanten ongelijk of vergelijkbaar kunnen zijn. Wegen met kleine aantallen gegroepeerde munten lijken geen voordeel te hebben ten opzichte van wegingen met enkele munten.
Dit geldt voor:
Zes munten: één tot twee lichte munten; w = 4.
Zeven munten: één tot drie lichte munten; w = 5.
Acht munten: één tot drie lichte munten; w = 6. Deze oplossing heeft een eenvoudige structuur:
- Doe eerst vier wegingen van de ene munt tegen de andere. Alle munten zijn gebruikt.
- In het slechtste geval: alle vier de wegingen zijn gebalanceerd (er zijn twee lichte munten die elkaar in evenwicht houden).
- Volgende twee wegingen: Weeg een munt van 1 tegen een munt van 2; weeg op dezelfde manier een munt vanaf een gewicht van 3 tegen een munt vanaf een gewicht van 4.
- Een van deze wegingen zal onevenwichtig zijn, waardoor de twee lichte munten worden geïdentificeerd. We zijn klaar in zes wegingen.
Sorry, onze reeks van 0, 0, 1, 2, 3, 4, 5, 6 is zeker niet interessant genoeg om aan de Online Encyclopedia of Integer-reeksen!
As Jonas Tøgersen Kjellstadli gewezen, lijkt de oplossing te zijn w = n − 2 voor kleine getallen, maar we hebben niet bewezen dat dit voor grotere getallen niet zal veranderen. Bij sommige n, het gebruik van meerdere muntwegingen zou het beter kunnen doen, of meer wegingen dan n − 2 kan nodig zijn. We kunnen de oplossing voor acht munten eenvoudig veralgemenen naar alle machten van 2, geven n − 2 als bovengrens voor het aantal wegingen voor alle machten van 2.
Mark Pearson besprak de gelijkenis van dit probleem met foutcorrigerende codes en stelde voor een informatietheoretische benadering te gebruiken op basis van het aantal mogelijke uitkomsten. Door een dergelijke aanpak te gebruiken, Mike Roberts plaatste een ondergrens voor het meer algemene geval, welke Rainer uit de lente een benadering voor afgeleid. Rainer plaatste ook een bovengrens uit een gepubliceerd artikel, maar merkte op dat de grenzen niet scherp zijn voor laag n en daarom niet nuttig voor de kleine aantallen die we hierboven hebben besproken. Dus voor zeven munten geven de genoemde grenzen een bereik van 4 tot 16, waar ons antwoord, 5, tussen valt. J Payette geeft extra wiskundige referenties en grenzen voor alle puzzels.
Bedankt aan iedereen die heeft deelgenomen. De Insights-prijs voor deze maand gaat gezamenlijk naar Ted en Rainer aus dem Spring. Gefeliciteerd!
Tot de volgende keer voor nieuw Insights.
