Hoe los ik het probleem van de 1000 criminelen op?

Jos, 65 jaar
20 mei 2015

In een oud nummer van het tijdschrift "Natuur en Techniek" (einde jaren 1960) stond een vraagstukje dat ongeveer als volgt geformuleerd was: 1000 criminelen genummerd van 1 tot 1000 worden in een circel geplaatst. Elke derde crimineel wordt geexecuteerd. Aan de laatste 2 overblijvers wordt gratie verleend. Welke volgnummers hebben deze 2?

Antwoord

Het antwoord is: 226 en 604. De uitleg hierover heb ik in een apart documentje neergeschreven dat je hier kunt downloaden.

Mijn oplossing is vrij omslachtig en ik zou zeer geïnteresseerd zijn in een eenvoudigere oplossingsmethode. Uiteraard zijn we niet geïnteresseerd in de naïeve oplossingsmethode die er zou in bestaan het gebeuren helemaal met de hand (of met de computer) na te bootsen.

Prof. Dr. Jan Van den Bussche, Universiteit Hasselt.

---

Reactie van Prof. Hendrik Van Maldeghem (Universiteit Gent).

Ik weet niet of de volgende oplossingsmethode eenvoudiger is, het vergt wel iets minder rekenwerk, denk ik. De methode is niet algemeen in die zin dat het voor willekeurige getallen gaat, maar wel in die zin dat het voor getallen tot 6 miljard (het totaal aantal mensen op aarde, meer criminelen kunnen er nooit zijn) nog steeds met de hand doenbaar is met minder dan 100 berekeningen. Het belangrijkste voordeel is dat de methode handig is om het raadsel op te lossen voor een ander aantal criminelen.

Ik gebruik inductie. Ik zal het concreet uitleggen met 1000 en 1001. We weten het antwoord voor 1000, stel dat er nu 1001 criminelen zijn. We beginnen dan de executie met het nummer drie, Maar dan zijn er maar 1000 meer over, en we weten dat dan de nummers 604 en 226 overblijven. Maar we beginnen te rekenen vanaf nummer 4 (want we hebben net nummer 3 geëxecuteerd en tellen verder vanaf 4). Dus de criminelen die nu zullen overblijven dragen de nummers 3+604=607, en 3+226=229 (als 1 4 wordt, dan wordt 604 607). We moeten er dus gewoon 3 bijtellen. Dit lijkt heel eenvoudig, ware het niet dat je soms in moeiljkheden komt als de overblijvende criminelen zich dicht bij de laatste nummers bevinden.

We doen even verder. Met 1002 criminelen blijven 610 en 232 over, ik doe er nu eens 100 bij: met 1102 criminelen blijven 3 maal 100 plus 610, en drie maal honderd plus 232 over, dus dat zijn 910 en 532. Ik doe er nog eens 96 bij: indien er 1198 criminelen zijn, dan blijven over: 910+(3.96)=1198 en 532+(3.96)=820. Hier blijft dus de laatste crimineel over. Wat gebeurt er nu indien we 1199 criminelen hebben? De derde crimineel valt weg, er blijven nog 1198 over, waarvan nummer 1198 overblijft. Maar we zijn (her)begonnen bij de vierde, de derde was al weg, dus het is nummer 2 die in onze nieuwe nummering numer 1198 is (dat is de nieuwe laatste als we met nummer 4 beginnen). Maar 2 is nu gelijk aan 1198 + 3 modulo 1199. Dus telkens we met het rangnummer van een overblijvende de grens van het aantal criminelen overschrijden, moeten we modulo het aantal nieuwe criminelen rekenen.

We passen dit eens toe op de kleine getallen om te zien of dit goed werkt. Met 3 criminelen blijven 1 en 2 over. Met 4 blijven over: 1+3 en 2+3 modulo 4. dat zijn 4 en 1, klopt! Met 5 criminelen blijven over 4+3 en 1+3 modulo 5, dat zijn 2 en 4. Met 6 blijven over 2+3 en 4+3 modulo 6, dus 5 en 1. Moeten we nu op die manier tot 1000 gaan om het uiteindelijke antwoord te vinden? Neen, zolang het bijtellen van 3 het aantal criminelen niet overschrijdt, kunnen we het modulorekenen negeren. We moeten dus alleen weten wanneer de overblijvende criminelen rangnummer 1 of 2 hebben. Dan kunnen we zonder moeite de grotere aantallen aan door gewoon een veelvoud van 3 bij te tellen. En daarvoor stellen we vier formules op.

Ik geef één voorbeeld. Stel rangnummer 1 komt voor bij het getal 2n (ik schrijf 2n omdat ik onderstel dat het aantal even is; het blijkt dat er twee verschillende redeneringen nodig zijn, eentje voor even getallen, eentje voor oneven). Dan komt 4 voor bij 2n+1, 7 bij 2n+2, enz. Bij 3n-1=2n+(n-1) criminelen blijft dan nummer 1+3(n-1)=3n-2 over. Bij 3n criminelen blijft dan over: 3n-2+3 modulo 3n, dat is rangnummer 1. Dus onze regel is: schiet 1 over bij 2n, dan schiet 1 ook over bij 3n. Op dezelfde manier leiden we af dat, indien 2 overchiet bij 2n criminelen, dan ook 2 bij 3n criminelen. Voor oneven aantallen zijn de regels: schiet rangnummer 1 over bij 2n+1 criminelen, dan schiet rangnummer 2 over bij 3n+2 criminelen, en schiet 2 over bij 2n+1, dan 1 bij 3n+1. Op die manier stellen we een kleine tabel samen, met het aantal criminelen waarbij rangnummers 1 of 2 overschieten. We zoek het antwoord voor 1000, dus we gaan daar niet over.

We verkrijgen: Bij 3 criminelen schiet 1 over: ik schrijf 3/1. 3=2.1+1, onze regel hierboven geeft dat 2 overschiet bij 3.1+2=5. 5=2.2+1, onze regel hierboven geeft dat 1 overschiet bij 3.2+1=7. Nogmaals de regel toepassen (7=2.3+1) geeft 2 schiet over bij 3.3+2=11. Enz. De getallen gaan gestaag de hoogte in: 3/1 5/2 7/1 2/11 16/1 24/1 36/1 54/1 81/1 122/2 183/2 274/1 411/1 617/2 925/1 Vanaf hier rekenen we verder met veelvouden van 3: 75 criminelen bij verhoogt het rangnummer van de overblijvende met 3 keer 75, dus met 225, en dat geeft nummer 226 die overblijft. Het zelfde doen we nu met nummer 2 die overblijft met 3 criminelen: 3/2 4/1 6/1 9/1 14/2 21/2 31/1 47/2 70/1 105/1 158/2 237/2 355/1 533/2 799/1 Vanaf hier 3x201 bijtellen, geeft 603+1=604. Deze methode vergt dus, behalve het denkwerk, twee berekeningen per verhoging van het aantal criminelen met 3/2. Dit zijn tussen de 5 en 6 per vertienvoudiging van het aantal criminelen.

Met bovenstaande tabellen kan je het vraagstuk oplossen voor alle aantallen tot 1200. Bijvoorbeeld, voor 500 criminelen schieten over: 1+3x89=268 en 1+3x145=436. Dus conclusie: om een specifiek geval op te lossen is deze methode wellicht evenwaardig aan deze van Jan, je dient ook een tabel te maken. Maar om verschillende gevallen op te lossen is deze methode veel gemakkelijker omdat de tabellen gelden voor alle gevallen, en je niet steeds opnieuw hoeft te beginnen. Maar kijk, twee totaal verschillende oplossingsmethodes, en beide komen hetzelfde uit, prachtig toch die wiskunde!

 

Reacties op dit antwoord

  • 24/05/2015 - Jan (wetenschapper)

    Aangezien Arno geen concreet antwoord geeft had ik graag nog willen reageren op dit heel leuk vraagstuk. Het antwoord is: 226 en 604. De uitleg hierover heb ik in een apart documentje neergeschreven dat je online kan terugvinden: http://alpha.uhasselt.be/jan.vandenbussche/1000criminelen.pdf Mijn oplossing is vrij omslachtig en ik zou zeer geïnteresseerd zijn in een eenvoudigere oplossingsmethode. Uiteraard, zoals reeds aangegeven door Arno, zijn we niet geïnteresseerd in de naieve oplossingsmethode die er zou in bestaan het gebeuren helemaal met de hand (of met de computer) na te bootsen. Jammer genoeg is de uitleg die Arno geeft niet helemaal correct. In de eerste ronde worden alle veelvouden van 3 tussen 1 en 1000 geschrapt. Dat zijn er 333 in aantal. Volgens de logica van Arno wordt vervolgens het 334ste veelvoud van 3 geschrapt, weliswaar modulo 1000. Nu is 334 * 3 = 1002; modulo 1000 is dit 2. Dit klopt ook. Maar, steeds de logica van Arno volgend, zou vervolgens (335 * 3) mod 1000=5 geschrapt worden. Dit klopt niet meer. Immers, de getallen 3 en 6 zijn reeds geschrapt, dus de drie getallen volgend op 2 zijn 4, 5 en 7. Het is dus 7 die nu aan de beurt is om geschrapt te worden.

  • 28/05/2015 - Hendrik (wetenschapper)

    Ik weet niet of de volgende oplossingsmethode eenvoudiger is, het vergt wel iets minder rekenwerk, denk ik. De methode is niet algemeen in die zin dat het voor willekeurige getallen gaat, maar wel in die zin dat het voor getallen tot 6 miljard (het totaal aantal mensen op aarde, meer criminelen kunnen er nooit zijn) nog steeds met de hand doenbaar is met minder dan 100 berekeningen. Het belangrijkste voordeel is dat de methode handig is om het raadsel op te lossen voor een ander aantal criminelen. Ik gebruik inductie. Ik zal het concreet uitleggen met 1000 en 1001. We weten het antwoord voor 1000, stel dat er nu 1001 criminelen zijn. We beginnen dan de executie met het nummer drie, Maar dan zijn er maar 1000 meer over, en we weten dat dan de nummers 604 en 226 overblijven. Maar we beginnen te rekenen vanaf nummer 4 (want we hebben net nummer 3 geëxecuteerd en tellen verder vanaf 4). Dus de criminelen die nu zullen overblijven dragen de nummers 3+604=607, en 3+226=229 (als 1 4 wordt, dan wordt 604 607). We moeten er dus gewoon 3 bijtellen. Dit lijkt heel eenvoudig, ware het niet dat je soms in moeiljkheden komt als de overblijvende criminelen zich dicht bij de laatste nummers bevinden. We doen even verder. Met 1002 criminelen blijven 610 en 232 over, ik doe er nu eens 100 bij: met 1102 criminelen blijven 3 maal 100 plus 610, en drie maal honderd plus 232 over, dus dat zijn 910 en 532. Ik doe er nog eens 96 bij: indien er 1198 criminelen zijn, dan blijven over: 910+(3.96)=1198 en 532+(3.96)=820. Hier blijft dus de laatste crimineel over. Wat gebeurt er nu indien we 1199 criminelen hebben? De derde crimineel valt weg, er blijven nog 1198 over, waarvan nummer 1198 overblijft. Maar we zijn (her)begonnen bij de vierde, de derde was al weg, dus het is nummer 2 die in onze nieuwe nummering numer 1198 is (dat is de nieuwe laatste als we met nummer 4 beginnen). Maar 2 is nu gelijk aan 1198 + 3 modulo 1199. Dus telkens we met het rangnummer van een overblijvende de grens van het aantal criminelen overschrijden, moeten we modulo het aantal nieuwe criminelen rekenen. We passen dit eens toe op de kleine getallen om te zien of dit goed werkt. Met 3 criminelen blijven 1 en 2 over. Met 4 blijven over: 1+3 en 2+3 modulo 4. dat zijn 4 en 1, klopt! Met 5 criminelen blijven over 4+3 en 1+3 modulo 5, dat zijn 2 en 4. Met 6 blijven over 2+3 en 4+3 modulo 6, dus 5 en 1. Moeten we nu op die manier tot 1000 gaan om het uiteindelijke antwoord te vinden? Neen, zolang het bijtellen van 3 het aantal criminelen niet overschrijdt, kunnen we het modulorekenen negeren. We moeten dus alleen weten wanneer de overblijvende criminelen rangnummer 1 of 2 hebben. Dan kunnen we zonder moeite de grotere aantallen aan door gewoon een veelvoud van 3 bij te tellen. En daarvoor stellen we vier formules op. Ik geef één voorbeeld. Stel rangnummer 1 komt voor bij het getal 2n (ik schrijf 2n omdat ik onderstel dat het aantal even is; het blijkt dat er twee verschillende redeneringen nodig zijn, eentje voor even getallen, eentje voor oneven). Dan komt 4 voor bij 2n+1, 7 bij 2n+2, enz. Bij 3n-1=2n+(n-1) criminelen blijft dan nummer 1+3(n-1)=3n-2 over. Bij 3n criminelen blijft dan over: 3n-2+3 modulo 3n, dat is rangnummer 1. Dus onze regel is: schiet 1 over bij 2n, dan schiet 1 ook over bij 3n. Op dezelfde manier leiden we af dat, indien 2 overchiet bij 2n criminelen, dan ook 2 bij 3n criminelen. Voor oneven aantallen zijn de regels: schiet rangnummer 1 over bij 2n+1 criminelen, dan schiet rangnummer 2 over bij 3n+2 criminelen, en schiet 2 over bij 2n+1, dan 1 bij 3n+1. Op die manier stellen we een kleine tabel samen, met het aantal criminelen waarbij rangnummers 1 of 2 overschieten. We zoek het antwoord voor 1000, dus we gaan daar niet over. We verkrijgen: Bij 3 criminelen schiet 1 over: ik schrijf 3/1. 3=2.1+1, onze regel hierboven geeft dat 2 overschiet bij 3.1+2=5. 5=2.2+1, onze regel hierboven geeft dat 1 overschiet bij 3.2+1=7. Nogmaals de regel toepassen (7=2.3+1) geeft 2 schiet over bij 3.3+2=11. Enz. De getallen gaan gestaag de hoogte in: 3/1 5/2 7/1 2/11 16/1 24/1 36/1 54/1 81/1 122/2 183/2 274/1 411/1 617/2 925/1 Vanaf hier rekenen we verder met veelvouden van 3: 75 criminelen bij verhoogt het rangnummer van de overblijvende met 3 keer 75, dus met 225, en dat geeft nummer 226 die overblijft. Het zelfde doen we nu met nummer 2 die overblijft met 3 criminelen: 3/2 4/1 6/1 9/1 14/2 21/2 31/1 47/2 70/1 105/1 158/2 237/2 355/1 533/2 799/1 Vanaf hier 3x201 bijtellen, geeft 603+1=604. Deze methode vergt dus, behalve het denkwerk, twee berekeningen per verhoging van het aantal criminelen met 3/2. Dit zijn tussen de 5 en 6 per vertienvoudiging van het aantal criminelen. Met bovenstaande tabellen kan je het vraagstuk oplossen voor alle aantallen tot 1200. Bijvoorbeeld, voor 500 criminelen schieten over: 1+3x89=268 en 1+3x145=436. Dus conclusie: om een specifiek geval op te lossen is deze methode wellicht evenwaardig aan deze van Jan, je dient ook een tabel te maken. Maar om verschillende gevallen op te lossen is deze methode veel gemakkelijker omdat de tabellen gelden voor alle gevallen, en je niet steeds opnieuw hoeft te beginnen. Maar kijk, twee totaal verschillende oplossingsmethodes, en beide komen hetzelfde uit, prachtig toch die wiskunde!

Enkel de vraagsteller en de wetenschapper kunnen reageren op een antwoord.

Beantwoord door

 Jan Van den Bussche

informatica bio-informatica ecologie

Universiteit Hasselt
Agoralaan Universitaire Campus-gebouw D BE-3590 Diepenbeek
http://www.uhasselt.be/

Zoek andere vragen

© 2008-2022
Ik heb een vraag wordt gecoördineerd door het
Koninklijk Belgisch Instituut voor Natuurwetenschappen