Je leest:

Het Collatz-probleem: ’t lijkt zo simpel

Het Collatz-probleem: ’t lijkt zo simpel

Het vermoeden van Collatz lijkt een simpel probleem uit de getaltheorie. Maar schijn bedriegt. Heel even leek het erop dat het 70 jaar oude vraagstuk was opgelost, maar de euforie verdween al snel.

Neem de laatste twee cijfers van je geboortejaar. Tel daarbij op hoe oud je in 2011 geworden bent, en er komt altijd 111 uit, althans, als je in de vorige eeuw geboren bent. Meestal maken wiskundigen zich niet al te druk over dit soort rekensommetjes die altijd op hetzelfde getal uitkomen, de verklaring is vaak na even logisch nadenken wel te vinden. Mocht je er toch niet zelf uitkomen, lees dan het kader “Geboortejaar en leeftijd”.

Het vermoeden van Collatz is echter zo’n sommetje waar wiskundigen zich wél druk over maken. Welk positief geheel getal je ook neemt, na het toepassen van twee vaste rekenregels kom je altijd op 1 uit, zegt het vermoeden.

Al 70 jaar lang is het niemand gelukt om het ogenschijnlijk simpele probleem te bewijzen of te weerleggen. Maar in het weekend van Hemelvaart kondigde Gerhard Opfer, een Duitse wiskundige uit Hamburg, ineens aan dat hij een bewijs had. Een pdf van zijn preprint is hier te vinden.

Wat is het vermoeden van Collatz?

Neem een willekeurig positief geheel getal. Is het even? Deel het door 2. Is het oneven? Vermenigvuldig het met 3 en tel er 1 bij op. Blijf deze stappen voor even en oneven herhalen.

Large
Eindigt elk natuurlijk getal op 1?

Neem bijvoorbeeld 84: dit geeft achtereenvolgens 42, 21, 64, 32, 16, 8, 4, 2, 1. Het vermoeden van Collatz zegt dat met deze twee rekenregels elk willekeurig positief geheel getal uiteindelijk op 1 zal uitkomen. De Duitse wiskundige Lothar Collatz (1910-1990) formuleerde dit vermoeden in 1937.

Bloggers rekenen af met Opfers bewijs

De internetgeneratie heeft sinds een paar jaar een nieuwe manier van wiskunde bedrijven ontdekt: via blogs. Openbaar, iedereen kan meekijken en reageren. Brent Yorgey, een promovendus van de universiteit van Pennsylvania, is zo iemand: al een paar dagen nadat Opfer zijn preprint openbaar had gemaakt, rekende hij via zijn blog af met diens ‘bewijs’. En hij was niet de enige. Hier is nog een andere blogger die geen spaan heel hield van het vermeende bewijs. En zo zijn er nog wel meer die zeggen dat Opfer zijn claim niet waar kan maken.

Geboortejaar en leeftijd

Het puzzeltje waarmee dit artikel begint, over geboortejaar en leeftijd, volgt automatisch uit het concept ‘leeftijd’. Ga maar na: neem je hele geboortejaar in plaats van alleen de laatste twee cijfers. Tel daarbij op hoe oud je dit jaar zult worden. Er zal dan altijd precies het jaar uitkomen waarin je nu leeft. Neem in plaats van je hele geboortejaar alleen de laatste twee cijfers, en er zal voor iedereen die vóór 2000 geboren is 111 uitkomen.

Yorgey schetst in zijn post een ‘bewijs’ van het vermoeden van Collatz, ongeveer als volgt. We doorlopen het Collatz-algoritme ‘achterwaarts’, dat wil zeggen: we beginnen bij 1 en kijken dan op welke getallen we uit kunnen komen. Als een getal gelijk is aan een drievoud plus één, zijn er twee mogelijkheden: je kunt het getal verdubbelen, of je kunt er 1 vanaf trekken en dan door 3 delen.

Andere getallen kun je alleen maar verdubbelen. Dus startend met 1 krijg je vervolgens 2, vanuit 2 krijg je 4, vanuit 4 krijg je 8 óf 1 (twee mogelijkheden, want 4 is een drievoud plus één), vanuit 8 krijg je 16, vanuit 16 krijg je 32 óf 5, enzovoorts. Zo doorgaand, krijg je een oneindige ‘boom’ waarvan 1 de ‘wortel’ is. Vanuit 1 kun je elk natuurlijk (dat wil zeggen positief, geheel) getal dat je maar wilt vinden in deze boom, ergo: elk natuurlijk getal moet op 1 eindigen als je het Collatz-algoritme uitvoert.

Yorgey realiseert zich natuurlijk dat dit helemaal geen bewijs is en dat schrijft hij ook (“Do you see the problem with this ‘proof’?”). Volgens hem geeft Opfer een ‘bewijs’ dat hier qua vorm ongeveer mee overeenkomt, en dus van geen kant deugt.

Nadat Yorgey had geblogd over Opfers bewijs, mengden verschillende personen zich in de discussie. De reacties op Yorgeys post lopen nogal uiteen; sommigen vinden de toon waarop hij over Opfer spreekt arrogant, waarvoor Yorgey in een vervolgbericht dan weer zijn excuses aanbiedt. Opfer heeft inmiddels ook zelf toegegeven dat zijn bewijs niet waterdicht is, schrijft Der Spiegel.

Fundamentele eigenschap

Waarom maken wiskundigen zich druk om zulke rekensommetjes? Omdat ze willen doorgronden hoe getallen werken. Als het vermoeden van Collatz inderdaad juist is, betekent het dat getallen een eigenschap hebben die er voor zorgt dat ze altijd aan deze twee rekenregels voldoen.

Die eigenschap geldt dan voor alle natuurlijke getallen. En daar houden wiskundigen van: want als iets altijd geldt, dan is het een fundamentele eigenschap van het concept ‘natuurlijk getal’.

Bijzonder aan het vermoeden van Collatz is dat het al ruim 70 jaar oud is. Dat betekent dat er al 70 jaar lang mensen bezig zijn om met getallenvoorbeelden te testen of er inderdaad altijd 1 uit komt. Met de komst van computers werd het natuurlijk helemaal makkelijk om veel getallen uit te proberen, en in al die jaren is er echter nog nooit een getal gevonden dat er niet aan voldoet. Maar dat is natuurlijk nog geen bewijs, en al helemaal niet voldoende om te begrijpen welke fundamentele eigenschap er achter zit.

Meer over het Vermoeden van Collatz:

Dit artikel is een publicatie van NEMO Kennislink.
© NEMO Kennislink, sommige rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 17 juni 2011

Discussieer mee

Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

LEES EN DRAAG BIJ AAN DE DISCUSSIE