Weegpuzzel

Weegpuzzels zijn logische puzzels waarbij het erom gaat om met behulp van een balans met twee schalen, maar zonder gewichten, te achterhalen welke van een aantal voorwerpen die er gelijk uitzien, een afwijkend gewicht hebben; en dit met zo weinig mogelijk wegingen, of met niet meer dan een vooraf vastgesteld aantal wegingen.

Munten wegen

Een klassiek voorbeeld is het probleem om een valse munt, die te licht of te zwaar is, te vinden in een verzameling van verder identieke munten:

We hebben 12 munten die er gelijk uitzien maar waarvan er een afwijkend gewicht heeft; ze kan zwaarder zijn of lichter dan de andere. Vind de afwijkende munt met niet meer dan drie wegingen, en zeg of die te licht of te zwaar is.

Bij de aanvang zijn er dus 24 mogelijkheden: elk van de 12 munten kan de valse zijn, en die kan te licht of te zwaar zijn.

Dit probleem kreeg in de jaren 1940 de nodige aandacht in de wiskundige vakpers; daarbij werd gezocht naar het grootste aantal munten waarin met n wegingen een valse munt kan gevonden worden. Het werd bewezen dat n wegingen volstaan voor een groep van (3ⁿ-3)/2 munten voor n groter of gelijk aan drie; dus 12 munten met drie wegingen, 39 munten met vier wegingen, 120 munten met vijf wegingen, enz.

Oplossing

We verdelen de munten in drie groepen van vier en wegen de eerste twee groepen tegen elkaar.

• Als de balans in evenwicht is, zijn al de gewogen munten goed. De valse munt zit in de derde groep. Voor de tweede weging plaatsen we drie munten uit de derde groep op een schaal en drie goede munten op de andere schaal.
  • Als de balans opnieuw in evenwicht is, moet de vierde, niet gewogen munt uit de derde groep de valse zijn. Door die te wegen tegen een goede munt weten we of ze te licht of te zwaar is.
  • Als de goede munten te zwaar blijken, is een van de drie munten uit groep drie de valse en is die te licht. We nemen voor de derde weging twee van die drie munten en wegen ze tegen elkaar af. Als de balans in evenwicht is, was de derde munt de valse. In het andere geval is de lichtste van de twee de valse.
  • Als de goede munten te licht zijn, is een van de drie munten uit groep drie de valse en is die te zwaar. Op dezelfde manier als hierboven kunnen we in een derde weging de valse munt vinden.

• Als de balans niet in evenwicht is, weten we dat de vier niet-gewogen munten in de derde groep goed zijn. Voor de tweede weging nemen we drie munten weg van de zware kant, verplaatsen drie munten van de lichte kant naar de zware kant, en plaatsen drie "goede" munten aan de lichte kant.
  • Als de balans nu in evenwicht is, betekent dit dat een van de drie munten die we van de zware kant wegnamen te zwaar is. Om te bepalen welke, wegen we twee van die drie munten. Als de balans in evenwicht is, is de derde munt de valse; anders is het de zwaarste van de twee.
  • Als de zware kant van de balans dezelfde is als bij de eerste weging, betekent dit ofwel dat de resterende munt aan de lichte kant te licht is, ofwel dat de resterende munt aan de zware kant te zwaar is. Uitsluitsel hierover krijgen we door een van die twee munten te wegen tegen een goede munt.
  • Als de balans anders uitslaat, zodat de kant die eerst te zwaar was nu te licht is, dan betekent dit dat een van de drie munten die van de lichte naar de zware kant verplaatst zijn, te licht is. We wegen twee van die drie munten. Als de balans in evenwicht is, is de derde munt de valse; anders is het de lichtste van de twee.

Varianten

In een andere versie van het probleem is het niet zeker of er wel een valse munt is; er kan er een of geen zijn.

Soms vraagt men enkel om de valse munt te identificeren en niet of ze te zwaar of te licht is. In dat geval kunnen we het probleem met 13 munten in drie wegingen oplossen: we leggen een van de dertien opzij en als de valse munt niet gevonden wordt bij de andere twaalf is het automatisch deze dertiende.

Als we vooraf weten dat de valse munt te licht is, kunnen we met drie wegingen uit 27 munten de valse munt bepalen (of algemeen met n wegingen uit 3ⁿ munten). We verdelen de munten in drie groepen van negen en wegen twee daarvan tegen elkaar af. Als de balans in evenwicht is gaan we verder met de derde groep, anders met de lichtste van de twee die we gewogen hebben. We verdelen die groep weer in drie gelijke delen van drie munten en wegen twee daarvan tegen elkaar af; op dezelfde manier houden we na de tweede weging een drietal munten over waaronder de te lichte munt. Door twee van die drie af te wegen kunnen we de valse munt identificeren.

Externe links

• Munten wegen

Bronnen, noten en/of referenties