het 12 munten probleem


In een zak bevinden zich 12 munten, die er hetzelfde uitzien.
Maar bekend is dat er mogelijk één munt bij is, die lichter of zwaarder is dan de andere.
Ook is er een balans met aan elke kant een schaaltje waarmee de munten te wegen, dus te vergelijken, zijn.
Hoeveel wegingen zijn er nodig om die mogelijk afwijkende munt te vinden?

En in het algemeen:
    - uit hoeveel munten m kunnen we een afwijkende munt vinden als er w wegingen plaatsvinden?
En natuurlijk: hoe moeten de munten per weging over de schaaltjes worden verdeeld?

Codering van wegingen

Zie figuur hieronder
De linkerschaal omlaag noemen we situatie L, gelijk noemen we = en rechterschaal omlaag coderen we als R

Merk op, dat
    "L" betekent dat links de zwaardere of rechts de lichtere munt ligt.
    "=" betekent dat alle munten gelijk zijn
    "R" betekent dat links de lichtere- of rechts de zwaardere munt ligt.
Om ons te oriënteren schrijven we eens alle mogelijke uitkomsten op van twee wegingen.

Twee wegingen

We tellen in de volgorde "L" , "=" , "R" en van links naar rechts.
    weging 1weging 2
    LL
    =L
    RL
    L=
    ==
    R=
    LR
    =R
    RR
De uitkomst van regel "==" hoort bij de situatie "alle munten even zwaar".
Stel , dat wegingen "LL" hoort bij de situatie "munt 1 zwaarder". Dan hoort "RR" bij "munt 1 lichter".
Bij 2 wegingen zijn er 32 regels, waarvan één gelijk is aan "==" .
Het lijkt er dus op, dat met 2 wegingen een afwijkende munt uit (32 - 1) / 2 = 4 kan worden gevonden.

De regels 1...4 van de tabel zijn te koppelen aan munt 1..4 afwijkend.
Maar bekijk eens van regels 1...4 de linker kolom van de tabel: daar staat .........L = R L ...........3 letters.
Een letter (L of R) betekent dat de munt die aan die regel is gekoppeld aan de weging moet deelnemen.
Maar 3 munten zijn niet over twee schaaltjes te verdelen.
Daarom laten we wegingen "LL" en "RR" niet meedoen.
De tabel passen we wat aan:
    afwijkende
    munt
    weging 1weging 2
    1=L
    2RL
    3L=
    3R=
    2LR
    1=R
Het lijkt er dus op dat we met 2 wegingen één afwijkende munt uit m = (32 - 3) / 2 = 3 kunnen vinden.
Alleen staat nog niet vast hoe de munten per weging over de schaaltjes verdeeld moeten worden.
Laten we de munten om en om op het linker en rechter schaaltje leggen.
Nu de munten over de schaaltjes zijn verdeeld kunnen we per munt vaststellen of hij lichter ( - ) of zwaarder (+) is.
    muntafwijkingweging 1weging 2
    1 + =L
    2 - RL
    3 - L=
    3 + R=
    2 + LR
    1 - =R
merk op:
    "=" : munt doet niet mee aan weging
    "L" uitslag links geplaatst of "R" uitslag rechtsgeplaatst : munt zwaarder
    "L" uitslag rechts geplaatst of "R" uitslag linksgeplaatst : munt lichter

Het algemene geval voor w wegingen en m munten.

w wegingen leveren 3w combinaties op van de tekens "L" , "=" , en "R".
De weging "===" staat voor "alle munten gelijk".

Per kolom van de tabel komen alle tekens (L=R) even vaak voor.
Er zijn dus per kolom 3w - (3w / 3) = 2.3w-1tekens "L" of "R"
De ene helft van die regels hoort bij "munt i zwaarder" , de andere helft bij "munt i lichter".
Zodat er per weging 3w-1 munten over de twee schaaltjes verdeeld moeten worden.
Maar dat is niet mogelijk omdat het een oneven aantal is.

Daarom laten we de combinaties "LL...LL" en dus ook "RR...RR" niet meedoen.
Daardoor zijn er nu 2.3w-1 - 2 = 2(3w-1 -1) letters per kolom,
dus per weging moeten (3w-1 -1) munten over de schaaltjes worden verdeeld.
Dat is altijd een even aantal, dus geen probleem.

Bij w wegingen kunnen we een afwijkende munt vinden uit m = (3w - 3)/2 munten.
Per weging liggen er per schaaltje (3w-1 -1) / 2 munten

Drie wegingen en 12 munten

Bij 3 wegingen is m = 3(3-1) - 1 = 12, uit 12 munten kan één mogelijk afwijkende munt worden bepaald.
We maken een tabel als hierboven en vullen eerst in de kolommen "munt" , "weging 1" , "weging 2" en "weging 3".

Merk op, dat de regels met de uitslagen "LLL" , "===" , en "RRR" zijn weggelaten.
Omdat in de kolom van weging 3 de eerste 8 munten uitslag "L" hebben, nemen we afwisselend een + en een - afwijking
hebben voor een gelijke verdeling van de munten over de schaaltjes.
    muntafwijkingweging 1weging 2weging 3
    1+=LL
    2-RLL
    3+L=L
    4-==L
    5+R=L
    6-LRL
    7+=RL
    8-RRL
    9+LL=
    10-=L=
    11+RL=
    12-L==
    12+R==
    11-LR=
    10+=R=
    9-RR=
    8+LLR
    7-=LR
    6+RLR
    5-L=R
    4+==R
    3-R=R
    2+LRR
    1-=RR
Nu controleren of de munten per weging goed verdeeld zijn:

Merk op:
    + L en - R : linkerschaaltje
    - L en + R : rechterschaaltje
In de tabel hieronder betekent "L" plaatsing van de munt in het linkerschaaltje en "R" in het rechterschaaltje.
"- " betekent dat de munt niet deelneemt aan de weging.

Plaatsingstabel:
    muntweging 1
    schaal
    weging 2
    schaal
    weging 3
    schaal
    1-LL
    2LRR
    3L-L
    4--R
    5R-L
    6RLR
    7-RL
    8LLR
    9LL-
    10-R-
    11RL-
    12R--
We turven de kolommen voor elke weging en vinden

...weging 1:.........LLRRLLRR.........{4 maal linkerschaal en 4 keer rechterschaal, OK}
...weging 2:.........LRLRLLRL..........{5 maal linkerschaal en 3 keer rechterschaal, fout}
...weging 3:.........LRLRLRLR.........{4 maal linkerschaal en 4 keer rechterschaal, OK}

We moeten voor weging 2 een munt van het linker- naar het rechterschaaltje verplaatsen, zonder de andere metingen
te beïnvloeden.
Dat kan door de "+" en "-" afwijking van munten 9 en 12 te verwisselen.
Kolom 1 behoudt dan evenveel "L" als "R" voor de schaaltjes en kolom 2 verplaatst een munt naar het rechterschaaltje.

De plaatsingtabel wordt hiermee:

    muntweging 1
    schaal
    weging 2
    schaal
    weging 3
    schaal
    1-LL
    2LRR
    3L-L
    4--R
    5R-L
    6RLR
    7-RL
    8LLR
    9RR-
    10-R-
    11RL-
    12L--


De oorspronkelijke wegingentabel ziet er nu zo uit:
    muntafwijkingweging 1weging 2weging 3
    1+=LL
    2-RLL
    3+L=L
    4-==L
    5+R=L
    6-LRL
    7+=RL
    8-RRL
    9-LL=
    10-=L=
    11+RL=
    12+L==
    12-R==
    11-LR=
    10+=R=
    9+RR=
    8+LLR
    7-=LR
    6+RLR
    5-L=R
    4+==R
    3-R=R
    2+LRR
    1-=RR
En hiermee is het probleem opgelost.
Resteert nog een manier om vooraf door berekening het schaaltje van een munt per weging te bepalen.
Mooie toepassing van de lineaire algebra?