Het 12 munten probleem
Een nieuw en meer uitgebreid artikel vind je hier: www.davdata.nl/munten.html
Inleiding.
De 12 munten in een zakje zien er hetzelfde uit, maar misschien is er een
lichter of zwaarder dan de 11 andere. Hoeveel wegingen met een balans zijn
nodig om die lichtere of zwaardere munt te vinden? En hoe pak je zoiets aan?
Bij elke weging zijn er drie mogelijkheden:
1. de linkerschaal van de balans zakt omlaag. Noem dit L.
2. de balans blijft in evenwicht. Noem dit =.
3. de rechterschaal van de balans zakt omlaag. Noem dit R.
Het resultaat van elke weging kan dus met L,= of R worden aangeduid.
Een serie wegingen levert een code op, bijvoorbeeld L=R bij 3 wegingen:
bij de eerste weging gaat de linkerschaal omlaag, bij de tweede is er evenwicht
en bij de derde weging gaat de rechterschaal omlaag.
Bij een code hoort een bepaalde afwijkende (valse) munt.
De aanpak is als volgt:
- schrijf in een tabel alle mogelijke codes op
- koppel een code aan een afwijkende munt
- bepaal aan de hand van de codes de inhoud van de schalen per weging.
De code == (alleen = tekens) hoort natuurlijk bij "alle munten gelijk".
De code LLR hoort bij RRL.
Als LLR betekent "munt 3 zwaarder" dan is RRL uiteraard "munt 3 lichter".
Eerst eens 2 wegingen bekijken.
We koppelen de munten zonder nadenken aan de codes en zien wel.
De volgende resultaten zijn mogelijk:
| weging1 | weging2 | betekenis |
|---|
| L | L | munt 1 zwaarder |
| L | = | munt 2 zwaarder |
| L | R | munt 3 zwaarder |
| = | L | munt 4 zwaarder |
| = | = | munten gelijk |
| = | R | munt 4 lichter |
| R | L | munt 3 lichter |
| R | = | munt 2 lichter |
| R | R | munt 1 lichter |
Twee wegingen leveren 3 x 3 = 9 codes op.
Alle munten gelijk is 1 mogelijkheid.
Blijven over 8 mogelijkheden voor een lichtere of zwaardere munt,
zodat het lijkt alsof met twee wegingen een uit 8 / 2 = 4 munten is te
selecteren.
Koppelen we de uitslag "LL" aan munt1 zwaarder, dan volgt dat de
uitslag "RR" betekent: munt1 lichter.
We bepalen nu aan de hand van de tabel welke munten per weging in het linker-
of rechter schaaltje van de balans moeten liggen.
De munten nummeren we 1..4.
| weging | linkerschaal | rechterschaal |
| 1 | 1 2 3 | - - - |
| 2 | 1 - - | 3 4 - |
Bij zowel weging 1 als 2 moet dan munt1 op het linker schaaltje liggen.
Munt 2 moet bij de eerste weging links liggen en mag bij de tweede weging
niet meedoen.
Munt 3 moet bij de eerste weging links liggen en bij de tweede weging rechts.
Munt 4 mag bij de eerste weging niet meedoen en ligt rechts bij weging 2.
In de tabel hierboven zien we twee problemen:
1. de munten liggen niet goed verdeeld over de schaaltjes
2. elke weging betreft 3 munten en die zijn niet over 2 schaaltjes te verdelen
.
Beschouw in de code-tabel hierboven de regels LL .. =L .
Dat zijn (3*3 - 1)/2 = 4 regels.
Elke regel hoort bij een mogelijk afwijkende munt.
Een letter (L,R) betekent, dat die munt aan de weging moet meedoen.
Een = teken wil zeggen, dat die munt niet aan de weging mag meedoen.
We tellen 3 letters per kolom over de beschouwde 4 regels.
En 3 munten kunnen niet gelijk over de schaaltjes worden verdeeld.
We moeten per kolom van 1 letter afzien.
Dat kan, door de codes LL en RR niet te gebruiken.
De code-tabel passen we aan:
(de munten zijn nog steeds zonder nadenken aan de codes gekoppeld)
| weging1 | weging2 | betekenis |
|---|
| L | = | munt 1 zwaarder |
| L | R | munt 2 zwaarder |
| = | L | munt 3 zwaarder |
| = | = | munten gelijk |
| = | R | munt 3 lichter |
| R | L | munt 2 lichter |
| R | = | munt 1 lichter |
De plaatsing van de munten wordt nu:
| weging | linkerschaal | rechterschaal |
| 1 | 1 2 | - - |
| 2 | 3 - | 2 - |
Het aantal munten klopt, maar de verdelening over de schaaltjes is nog ongelijk.
Dat is te verhelpen door de betekenis van de codes wat aan te passen.
Om munt 1 bij de eerste weging in het rechter schaaltje te krijgen, moet de
betekenis van code L= worden gewijzigd van "munt-1 zwaarder" in "munt-1 lichter".
(code R= verandert dus mee)
De code tabel wordt nu:
| weging1 | weging2 | betekenis |
|---|
| L | = | munt 1 lichter |
| L | R | munt 2 zwaarder |
| = | L | munt 3 zwaarder |
| = | = | munten gelijk |
| = | R | munt 3 lichter |
| R | L | munt 2 lichter |
| R | = | munt 1 zwaarder |
De plaatsing wordt:
| weging | linkerschaal | rechterschaal |
| 1 | 2 | 1 |
| 2 | 3 | 2 |
Nu is de zaak in orde.
Aan de uitslag van twee wegingen is in de code-tabel af te lezen of er een munt afwijkt.
Met twee wegingen zijn dus 3 munten te testen.
Het algemene geval.
W wegingen leveren 3W verschillende codes.
Daarvan is er een "=....=" , voor "alle munten gelijk".
Blijft over 3w - 1 codes voor een ongelijke munt.
De tekens L,=,R komen in de codes evenvaak voor.
We beschouwen in de code-tabel de regels LL..LL tot en met ==...=L.
Voorbij code ==..== komen alleen symmetrische gevallen voor (licht - zwaar verwisseld).
In kolom 1 staan op deze regels 1/3 * 3w letters L.
Elke letter betekent, dat die munt aan de weging moet deelnemen.
Dat kan niet, want het is een oneven aantal.
Daarom laten we codes LL..LL en RR..RR niet meedoen.
Er blijven nu 3w - 3 codes over om een lichtere of zwaardere munt aan te duiden.
Daarom kunnen bij w wegingen m = (3w - 3) / 2 munten worden getest.
De volgende tabel is het gevolg van deze formule:
| aantal wegingen | aantal munten |
| 2 | 3 |
| 3 | 12 |
| 4 | 39 |
| 5 | 120 |
Vraag.
Stel eens, dat we over een normale munt beschikken, die aan elke weging
mag worden toegevoegd.
Het probleem van een oneven aantal munten bestaat dan niet meer.
Hoe zou de formule m = .... dan worden?
