In 1937 formuleerde Lothar Collatz (1910 - 1990, zie figuur hiernaast) het zogenaamde vermoeden van Collatz: welk positieve gehele getal `n` je ook kiest, als je er een rij bij maakt volgens het voorschrift:
dan kom je als je maar lang genoeg doorgaat altijd uiteindelijk uit op `1`.
Dat lijkt je vast wel een bijzonder vermoeden, dus je wilt misschien wel eens proberen of het klopt. En dan: klopt het ook echt altijd? Ook professionele wiskundigen bijten hun tanden daar nog steeds op stuk. Maar zelf erover puzzelen kan natuurlijk altijd! Je moet dan wel iets weten over rijen.
In dit hoofdstuk wordt het Collatzprobleem op een nette wiskundige manier geformuleerd.Je krijgt een aantal opgaven om je het probleem eigen te maken.
De Collatzfunctie `text(C)` met als domein de positieve gehele getallen is de functie met voorschrift:
`text(C)(n)=n/2` als `n` een even getal is
`text(C)(n)=3n+1` als `n` een oneven getal is
Bereken `text(C)(n)` voor `n=1,..., 10`
`text(C)(3)=10`
Pas de Collatzfunctie toe op de uitkomst `10` en je krijgt `text(C)(10)=5`
Twee keer toepassen van `text(C)` noteer je als `text(C)^2` dus `text(C)^2(3)=5`
Zo kun je doorgaan.
Als je de de Collatzfunctie herhaald toepast krijg je een rij positieve gehele getallen.
Bij startgetal `3` krijgen we: `3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1,..`
Bij `1` gaat de rij repeteren.
Onder de Collatzrij met startgetal `n` (`n` positief geheel) verstaan we de rij `n, text(C)(n), text(C)^2(n), text(C)^3(n), ..., text(C)^k(n), ...`
Waarschijnlijk heb je ontdekt dat bij elk van de startgetallen van opgave 2 de rij steeds bij `1` uitkomt en dan gaat repeteren. Zou dit altijd zo zijn? Het antwoord op deze vraag is niet zomaar duidelijk. Sterker nog: tot op heden hebben wiskundigen geen antwoord op deze vraag kunnen geven. Dit leidt tot het volgende vermoeden, de volgende hypothese:
Voor elk positief geheel startgetal `n` geldt: De Collatzrij met startgetal `n` komt uiteindelijk op `1` uit en gaat dan repeteren.
De hypothese is inmiddels getest voor alle getallen onder `2^68` en bleek steeds te kloppen. Dit is echter nog geen bewijs van de juistheid.
Bij de Collatzrij met startgetal `n` zijn er in theorie drie mogelijkheden:
De hypothese zegt dat voor elk positief geheel startgetal `n` de eerste mogelijkheid altijd optreedt.
Is de Collatzfunctie echt zo bijzonder of zijn er misschien ook andere functies die bij herhaald toepassen op een positief startgetal uiteindelijk altijd bij `1` gaan repeteren? In de volgende opgaven ga je dat testen met functies die een klein beetje afwijken van de Collatzfunctie `text(C)`.
De functie `text(D)` met als domein de positieve gehele getallen heeft het voorschrift:
`text(D)(n)=n/2` als `n` een even getal is
`text(D)(n)=3n-1` als `n` een oneven getal is
Pas de functie `text(D)` herhaald toe op elk van de startgetallen `1 .. 10`. Geldt de hypothese ook voor deze functie `text(D)`?
De functie `text(E)` met als domein de positieve gehele getallen heeft het voorschrift:
`text(E)(n)=n/2` als `n` een even getal is
`text(E)(n)=5n+1` als `n` een oneven getal is
Pas de functie `text(E)` herhaald toe op elk van de startgetallen `1 .. 10`. Geldt de hypothese ook voor deze functie `text(E)`?
De functie `text(F)` met als domein de positieve gehele getallen heeft het voorschrift:
`text(F)(n)=(2n)/3` als `n` een drievoud is
`text(F)(n)=(4n-1)/3` als `n` een drievoud plus `1` is
`text(F)(n)=(4n+1)/3` als `n` een drievoud plus `2`is
Pas de functie `text(F)` herhaald toe op elk van de startgetallen `1, ..., 8`. Geldt de hypothese ook voor deze functie `text(F)`?
De functie `text(G)` met als domein de positieve gehele getallen heeft het voorschrift:
`text(G)(1)=1`
`text(G)(n)=3n+1` als `n` een priemgetal is
`text(G)(n)=P` als `n>1` en geen priemgetal is. `P` is de grootste echte deler van `n`
Pas de functie `text(G)` herhaald toe op elk van de startgetallen `1, ..., 10`. Geldt de hypothese ook voor deze functie `text(G)`?
Stel dat ook negatieve getallen en het getal `0` in het domein van de Collatzfunctie opgenomen zouden worden.
Je kunt je afvragen hoe vaak de Collatzfunctie toegepast moet worden op een startgetal `n` tot voor het eerst het getal `1` wordt bereikt. Dit getal heet de tellerfunctie toegepast op `n` en wordt genoteerd als `text(T)(n)`.
Voor elk positief geheel getal is:
`text(T)(n)` is het aantal malen dat de Collatzfunctie toegepast moet worden op `n` voordat voor het eerst `1` bereikt wordt.
`text(T)(n)=oo` (oneindig) als `1` nooit bereikt wordt.
`text(T)` heet de tellerfunctie bij de Collatzfunctie.
Het laatste deel van de definitie moet erbij, aangezien er niet bewezen is dat bij elk startgetal de rij een keer op `1` uitkomt.
De hypothese wordt met de tellerfunctie:`text(T)(n)` is altijd een positief geheel getal.
Wikipedia geeft een aantal waarden voor `text(T)`:
De langste rij voor een startwaarde onder duizend, is `178` stappen lang voor de startwaarde `871`, ofwel: `text(T)(871) = 178`
De langste rij voor een startwaarde onder een miljoen, is `524` stappen lang voor de startwaarde `837799` ofwel `text(T)(837799)=524`.
De langste rij voor een startwaarde onder een miljard, is `986` stappen lang voor de startwaarde `670617279` ofwel `text(T)(670617279)=986`.
Je zou misschien verwachten dat met het groter worden van de startwaarde de teller evenredig toeneemt, maar dit lijkt uit deze voorbeelden niet het geval. Bij een toename van het startgetal van duizend naar miljoen (dus een toename met een factor `1000`) wordt het maximale aantal stappen slechts ongeveer drie keer zo groot. Bij een toename van een miljoen naar een miljard (wederom een factor `1000`) wordt het maximale stappen zelfs met minder dan twee vermenigvuldigd.
De functie `text(T)` heeft enkele leuke eigenschappen. Zo geldt bijvoorbeeld dat de waarde van `text(T)` voor elk `8`-voud `+4` gelijk is aan de waarde van `text(T)` voor datzelfde `8`-voud `+5`.
Te bewijzen: Voor elk positief geheel getal `n` geldt: `text(T)(8n+4)=text(T)(8n+5)`.
Bewijs:
De Collatzrij voor `8n+4` begint als volgt: `8n+4, 4n+2, 2n+1, 6n+4`
De Collatzrij voor `8n+5` begint als volgt: `8n+5, 24n+16, 12n+8, 6n+4`
Na driemaal toepassen van de Collatzfunctie komen de rijen dus op hetzelfde getal uit. Je kunt dus concluderen: `text(T)(8n+4)=text(T)(8n+5)` voor elk positief geheel getal `n`.#
Voor een poging tot een bewijs is de methode verloopsinductie van belang.
Verloopsinductie werkt als volgt:
Het begin is eenvoudig: de basis `n=1` is vanzelfsprekend.
Voor het bewijzen van de inductiestap kun je opmerken dat elk positief getal een `4`-voud `-1`, een `4`-voud, een `4`-voud `+1` of een `4`-voud `+2` is. Merk op dat je het tweede en vierde geval samen kunt nemen tot een `2`-voud (een even getal dus).
Voor het bewijzen van de inductiestap kun je dus drie gevallen onderscheiden:
Geval 1: `n+1=2k`
Pas de Collatzfunctie toe op `2k`, dan krijg je: `text(C)(2k)=k`.
Aangezien `k<=n` geldt de inductiehypothese: bij herhaaldelijk toepassen van de Collatzfunctie op startgetal `k`, komt de rij uiteindelijk uit op `1` en gaat dan repeteren.
Geval 2: `n+1=4k+1`
Pas drie keer de Collatzfunctie toe op startgetal `4k+1`, dan krijg je de rij:
`4k+1, 12k+4, 6k+2, 3k+1`.
Aangezien `3k+1<4k+1` geldt weer de inductiehypothese.
Geval 3: `n+1=4k-1`
Pas nu vier keer de Collatzfunctie toe op de rij met startgetal `4k–1`, dan krijg je de rij:
`4k-1, 12k-2, 6k-1, 18k-2, 9k-1`.
Hier loopt het bewijs spaak. Je weet niet wat het volgende getal in de rij is, aangezien het van `n` afhangt of `9k–1` even of oneven is. Verder is `9k-1>4k-1`, dus de inductiehypothese geldt niet.#
Je kunt proberen het bewijs te repareren door geval 3 in het 'bewijs' te splitsen in twee gevallen: `k` is even (dus `k=2m`, voor zekere `m`) en `k` is oneven (dus `k=2m+1` voor zekere `m`).
Je moet dan de volgende twee situaties onderzoeken: `n+1=8m-1` en `n+1=8m+3`.
Toon aan dat het bewijs ook nu niet rond te krijgen is.
Het resultaat tot zover is dat er nog steeds geen bewijs is voor de hypothese.
Stel dat de hypothese onwaar is. Dan zijn er startgetallen waarvoor de Collatzrij niet op `1` uitkomt. Noem de verzameling van deze startgetallen `V`. `V` heeft vanzelfsprekend een kleinste element. Dat kleinste element is niet even. (Waarom niet?) Dat kleinste element is ook geen viervoud plus één (Waarom niet?). Ergo het kleinste element van V moet van de vorm `4k-1` zijn. Voor een bewijs of een tegenspraak hoef je dus alleen nog maar naar de viervouden min één te kijken. Dit blijkt allemaal nog niet zo eenvoudig. Een bewijs is nog steeds niet geleverd. Ook is er nog geen tegenvoorbeeld gevonden. Opgave 13 De aangepaste Collatzfunctie `text(M)` met als domein de positieve gehele getallen heeft het voorschrift: `text(M)(n)=n/2` als `n` een even getal is `text(M)(n)=3n-1` als `n` een viervoud min `1` is `text(M)(n)=3n+1` als `n` een viervoud plus `1` is Bewijs dat voor elk positief geheel getal `n` geldt: De aangepaste Collatzrij komt op enig moment uit op `1` (Tip: gebruik verloopsinductie) De Collatzrij omgekeerd
Stel dat de hypothese onwaar is. Dan zijn er startgetallen waarvoor de Collatzrij niet op `1` uitkomt. Noem de verzameling van deze startgetallen `V`. `V` heeft vanzelfsprekend een kleinste element. Dat kleinste element is niet even. (Waarom niet?) Dat kleinste element is ook geen viervoud plus één (Waarom niet?). Ergo het kleinste element van V moet van de vorm `4k-1` zijn.
Voor een bewijs of een tegenspraak hoef je dus alleen nog maar naar de viervouden min één te kijken. Dit blijkt allemaal nog niet zo eenvoudig. Een bewijs is nog steeds niet geleverd. Ook is er nog geen tegenvoorbeeld gevonden.
De aangepaste Collatzfunctie `text(M)` met als domein de positieve gehele getallen heeft het voorschrift:
`text(M)(n)=n/2` als `n` een even getal is
`text(M)(n)=3n-1` als `n` een viervoud min `1` is
`text(M)(n)=3n+1` als `n` een viervoud plus `1` is
Bewijs dat voor elk positief geheel getal `n` geldt: De aangepaste Collatzrij komt op enig moment uit op `1`
(Tip: gebruik verloopsinductie)
Het getal in een Collatzrij dat voorafgaat aan `1` is `2`.
Op zijn beurt heeft `2` als voorganger `4`. In principe heeft `4` twee voorgangers, namelijk `8` en `1`.
Immers `text(C)(8)=4` en `text(C)(1)=4`. Het tweede geval is niet zo interessant, aangezien de rij dan repeteert, dus `1` noem je geen voorganger.
Kortom: de enige voorganger van `4` is `8`.
Als je begint met `1` en je kijkt naar de rij van voorgangers, dan krijg je eerst:
`1, 2, 4, 8, 16,`
`16` heeft twee voorgangers, namelijk `32` en `5`.
Dit kun je weergeven in een graaf: de zogeheten Collatzgraaf:
Een boom is een graaf zonder gesloten paden (dus zonder rondwegen)
Je kunt nu de hypothese herformuleren:
Aangezien de hypothese nog niet bewezen is, mag je nog niet spreken over een boom. Je weet immers niet of de graaf geen rondweg bevat. Voor het gemak zal ik verder wel steeds spreken over de boom of de Collatzboom.
Merk het verband op tussen de niveaus in de boom en de tellerfunctie T die eerder gedefinieerd is (zie definitie 2).
Op elk niveau in de graaf staat een aantal getallen. Dit aantal hangt af van het niveau.
Door de wijze waarop de boom boven getekend is, kun je spreken over kolommen in de boom.
De kolom wordt genoemd naar het eerste getal in de kolom.
Twee voorbeelden van kolommen:
`1,2,4,8,16,32,64,..`
`21,42,84,168,336,..`
Het getal op niveau `k` (`k=0, 1, 2, 3, ..`) in de eerstgenoemde kolom is `2^k`.
Het verhaal gaat, dat toen de hypothese in 1937 door Lothar Collatz geformuleerd was, veel wiskundigen het werk, waar zij mee bezig waren, uit hun handen lieten vallen om te proberen de hypothese te bewijzen. Voor zo'n eenvoudig geformuleerd probleem moest dit toch niet zo moeilijk zijn. Helaas! De waarheid bleek van een andere orde. Het leuke is dan weer dat je eeuwige roem kunt vergaren als het je lukt de hypothese te bewijzen (of te weerleggen natuurlijk).
Math4all Auteur: Rob Grünefeld
» Wikipedia over het vermoeden van Collatz
» Over Lothar Collatz (engelstalig)
Antwoorden van de opgaven
Ik wil mij aanmelden voor:
