Wiskundemeisjes

Ionica & Jeanine
 
Slik Internetbureau Rotterdam Internetbureau Rotterdam



  • Laatste Reacties

Categorieën

Archief

Gênante vragen


In Column, door Ionica

Deze column verscheen vandaag in de Volkskrant.

Mijn vriendin Cristel studeerde geschiedenis met als specialisatie achttiende-eeuwse dagboeken. Op feestjes belandt ze steevast naast iemand die werkelijk alles weet van de Peloponnesische oorlog. Als zo iemand hoort dat zij een historica is, dan verwacht hij dat ze daar uren met hem over kan praten. Cristel vindt het dan altijd een beetje gênant om toe te moeten geven dat zij helemaal niets weet van de Peloponnesische oorlog.

Als wiskundige kom je bijna nooit in zulke situaties, omdat de meeste mensen bij wiskunde niet verder komen dan de stelling van Pythagoras. Daarom was ik zo verbaasd toen iemand laatst op een borrel aan me vroeg hoe het zat met het vermoeden van Collatz.

Ik wist gelukkig wel wat het vermoeden van Collatz was. Het gaat over reeksen getallen. Je begint met een willekeurig geheel getal, groter dan nul. Als het getal even is, dan deel je het door twee. Als het getal oneven is, dan vermenigvuldig je het met drie en tel je er één bij op. Daarna herhaal je dit proces met de uitkomst, en opnieuw, en opnieuw.

Bijvoorbeeld:

6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

of

13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1.


Het resultaat als je begint bij 6, 9 of 42.

Het resultaat als je begint bij 6, 9 of 42.


Je stopt bij één, omdat je vanaf daar in een vicieuze cirkel belandt: één gaat immers naar vier en dan via twee weer terug naar één. Het vermoeden van Collatz is dat je altijd op één uitkomt, met welk getal je ook begint.

Probeer het zelf maar eens voor je lievelingsgetal. Als je getal kleiner is dan 10^18 dan kom je zeker op één uit, tot die grens is het vermoeden met de computer getest. Het aantal stappen kan behoorlijk groot worden: als je begint met een bescheiden 27 heb je bijvoorbeeld al 112 stappen nodig voor je bij 1 eindigt.

De meeste wiskundigen denken dat het vermoeden van Collatz waar is en dat je inderdaad voor elk getal bij één zult eindigen. Maar niemand heeft een bewijs. De in 1996 overleden wiskundige Paul Erdös verzuchtte volgens de overlevering dat de wiskunde nog niet klaar was voor dit soort moeilijke problemen. Voor de zekerheid loofde hij toch maar 500 dollar uit voor een oplossing. Die oplossing is er nog steeds niet.


Fijne grap van xkcd.com

Dit alles vertelde ik op de borrel. De getallenvoorbeelden zocht ik snel op met mijn telefoon, iets wat ik ook van harte aanraad bij lastige vragen over Peloponnesische oorlogen. De vragensteller keek me wat teleurgesteld aan. Dus dit kunnen wiskundigen níet oplossen? Wat zitten jullie dan de hele dag achter jullie bureaus te doen? En wat kunnen jullie wel?

Het is misschien gênant om een vraag te krijgen over een onderwerp waarvan je nog nooit hebt gehoord. Maar het is nog veel gênanter om toe te moeten geven dat jij en je vakgenoten een ogenschijnlijk eenvoudig probleem niet kunnen oplossen.

28 reacties op “Gênante vragen”

  1. Ionica:

    Frans Oort wees me nog op deze site waar je mooi online Collatz reeksen kan maken:
    http://members.chello.nl/k.ijntema/seqoddeven.html

  2. rienk:

    Goedemiddag,

    Wellicht denk ik er te simpel over maar het lijkt me logisch wanneer je zulke getallen sprongen gaat maken, Door het vermenigvuldigen en delen kom je vanzelf een keer uit op een getal uit de kwadraat reeks van 2.

    De keer drie is ook onzin volgens mij gewoon de even getallen delen door 2 en oneven getallen plus 1 doen geeft dezelfde uitkomst.

    Ik zie de specialiteit dus niet zo echter ik ben ook geen wiskundige.

    Groeten Rienk

  3. P:

    Rienk, het punt is dat je moet bewijzen dat je altijd(!) op die reeks uitkomt. En dat is vooralsnog niet gelukt. Het lijkt wel te kloppen, maar hoe weet je nu zeker of er niet ergens 1 getal is (die groter moet zijn dan 10^18) waarvoor het niet werkt?

  4. Joep:

    Toch ook een vraag: Waar komt die *3 vandaan? Is er een reden voor deze reeks te kiezen t.o.v. bijvoorbeeld *9+2 of gewoon +1?

  5. Walter:

    Weblogs met Cristel erin zijn altijd goed!

  6. ralph:

    Inderdaad, voor gewoon +1 is hij pretty obvious. Die *3 maakt het wel interessanter. Je zult dus moeten bewijzen dat voor iedere y geld dat als 2^(y-1) 2^y, de vergelijking 3/2*x+1/2 = 2^y altijd een oplossing kent voor x in N. Want alleen dan zul je met *3+1 altijd ergens op een macht van twee uitkomen. Het bewijs hiervoor ontgaat me, maar misschien morgenochtend onder de douche wat inspiratie.....

  7. ralph:

    edit: 2^(y-1) &lt x &gt 2&y

  8. ralph:

    groter dan en kleiner worden hier bedoeld. Latex is te lang geleden ;-)

  9. Rob van den TiIllaart:

    Als je het probleem statistisch bekijkt wordt duidelijk waarom de *3+1 zo interessant is. Gemiddeld zitten in een even getal 2 keer de factor 2. (bewijs zie URL onder) dus de even regel wordt gemiddeld 2 keer toegepast. De oneven regel wordt maar 1 keer toegepast want dan wordt het getal even.

    Dus gemiddeld krijg je na een oneven regel twee even regels. Het effect is dus:

    N' := (3N + 1) / 4 ~= 3/4 N !! 3/4 N is kleiner dan N

    Doe dit vaak genoeg en => N.(3/4)^p = 1.

    Als die factor 3 nu 5 of groter was dan zou N' ~= 5/4 N dus zou de reeks juist (statistisch gezien) blijven oplopen.

    NB dit is statistiek dus geen bewijs.

    Een uitvoeriger verhaal hierover zie:
    http://bit.ly/d1qcs3
    geschreven naar aanleiding van
    http://www.orthogonal.com.au/hobby/mm/hail/index.htm

    Een aardige oefening is om het probleem omgekeerd te benaderen. Vanuit ieder getal zijn 1 of 2 getallen te realiseren, altijd eentje met de even regel in zijn achteruit (x2) en soms een met de oneven regel in zijn achteruit (-1 /3). De verzameling gegenereerde getallen zou dan N moeten zijn.

    Verder vermoed ik sterk dat je deze stelling enkel voor de priemgetallen hoeft te bewijzen, maar dat moet nog een keer op papier uitgewerkt worden ...

    groet,
    Rob van den Tillaart
    - "You have lies, damned lies, and statistics" :)

  10. Martijn:

    Voor meer informatie over "mathematical disease":
    http://rjlipton.wordpress.com/2009/11/04/on-mathematical-diseases/

  11. Paul:

    Dit is een erg leuke uitdaging in de Volkskrant. Graag meer....

    Van het vermoeden van Collatz heb ik een Excel werkblad gemaakt om het na te rekenen. Het klopt inderdaad.

    Maar.... dan heeft Ionica een kleine vergissing gemaakt....
    Als je een berekening een stap noemt en het invullen van het startgetal dus geen stap is. Het getal 27 heeft dan namelijk geen 112 stappen nodig, maar 'slechts'111.

    Groetjes,

    Paul

  12. Pieter:

    Misschien een rare vraag, maar heeft het vinden van een sluitend bewijs ook nog nut voor een bepaalde toepassing van dit vermoeden?

  13. Cor Heideveld:

    Ik kom tot het bewijs om het probleem omgekeerd te bekijken.
    Stap 1--Als je een getal hebt in de reeks 2 factor n, kom je als je dat getal deelt door 2
    altijd uit op 1.
    Stap 2- als je een willekeurig getal neemt en de berekeningen maar lang genoeg uitvoert kom je altijd uit op een getal uit de reeks 2 factor n.
    Bewijs- Omdat je de uitvoering oneindig keer mag uitvoeren is voor ieder getal een oplossing om tussen 10 > 17 en oneindig in de reeks 2 factor n te komen d.m.v. matrix zou je het kunnen uitzetten in een grafiek.

    vriendelijke groeten Cor

  14. Reijer:

    @Cor: stap 2 hoeft echter helemaal niet waar te zijn. Je zou bijvoorbeeld een cyclische reeks kunnen krijgen waar geen enkele 2-macht in zit. Net zoals dat je met 4-2-1-4-2... oneindig door kunt gaan zonder ooit op bijvoorbeeld een oneven getal uit te komen.

  15. Martine Adema:

    genant dat een simpel probleem niet is opgelost: in de kledingwereld bestaat een soortgelijk probleem. We maken kleding op basis van ervaringsregels en niet op basis van een wetenschappelijke 3D naar 2D vertaling. We kunnen dus slechts bij benadering passende kleding maken. Ik weet onderhand waar de oplossing kan liggen. Deze oplossing is naar mijn mening puur wiskundig. Tot op heden hebben weinigen dit echter belangrijk genoeg gevonden om het werkelijk aan te pakken.
    Het noemen, beschrijven en bespreekbaar maken van het onderwerp in mijn eigen directe vakgebied, en daarbuiten, kost moeite en maakt kwetsbaar. Het aanpakken van de oplossing voelt altijd nog als een uitdaging, en ik heb besloten dat ik mijn tijd positief wil ervaren met de oplossingen die er nu wel zijn. Nog 10-20 jaar en dan is de wetenschappelijke oplossing voor handen. Ik hoop met het resultaat van de oplossing te mogen werken.

    vr grt Martine Adema

  16. Cor Heideveld:

    Reijer,
    Geef me een voorbeeld
    Cor

  17. Reijer:

    Cor, dat gaat helaas niet. Als er zo'n voorbeeld bekend zou zijn dan zou daarmee direct bewezen zijn dat het vermoeden van Collatz niet waar is. Geen voorbeeld kunnen bedenken is echter verre van een bewijs dat het niet kan.

  18. ralph:

    How about: je hebt twee bewerkingen, A en B. Na een bewerking A (de *3+1) volgt altijd een bewerking B. De reeks is dus te simplificeren door een nieuwe bewerking A' te introduceren die A*B is, oftwel: 3/2x+1/2. Dit is belangrijk want simplificeert de reeks.
    Op om 1 uit komen, moet dit voorafgegaan zijn door de omgekeerde bewerkingen (gedeeld door anderhalf, plus een half voor A', en x2 voor B). Dus ieder getal, om op 1 uit te komen, moet OF een macht van twee zijn, OF het product van een macht van 2 en een veelvoud van 3/2, plus een half. Dit mag dan in meerdere bewerkingsreeksen. Het is makkelijk aan te tonen dat dit zo is.

    Immers, de even getallen zijn deelbaar door een macht van twee (namelijk 2^1) en komen daarmee na bewerking B uit op een oneven getal. De helft van de oneven getallen zijn altijd een veelvoud van 1 1/2 ,plus 1/2. De andere helft van de oneven getallen kun je genereren door het getal eerst door twee te delen waarna een veelvoud van 1 1/2 + 1/2 overblijft. Nu vraag je je af waarom het opeens OK is wanneer je zo'n getal, bijvoorbeeld, 7, eerst door twee mag delen. Je komt dan uit op 3 1/2, en dat is natuurlijk geen heel getal en zou dus niet moeten mogen. Echter, dit gebeurt alleen als er een orignele A en B achter elkaar gebeuren in de reeks, en toen hadden we voor het gemak door twee gedeeld om de bewerkingen te kunnen aantonen. De 3 1/2 is dus eigenlijk geen 3 1/2, maar 7, en zou dus een veelvoud van 3, plus 1 moeten zijn, en dat issie. Anders gezegd: alle oneven getallen zijn een product van 3, plus 1, of een product van 1 1/2, plus 1/2. Daarom is de reeks van gegenereerde getallen N, en leiden alle reeksen naar 1.
    Heb ik iets gewonnen?

  19. Lex Boersma:

    De wiskundemeisjes vonden het wel genant dat een dergelijk simpel probleem niet is op te lossen. Dat is niet leuk,daarom bij deze het bewijs. Het bewijs is enigszins analoog aan het gegeven dat als je maar vaak genoeg met een dobbelsteen gooit, het gemiddelde op 3,5 uitkomt. Als je dat kan uitleggen danwel begrijpen, is dit wellicht ook te volgen.

    BEWIJS van vermoeden van Collatz:
    Een willekeurig getal is even of oneven. Er zijn evenveel even getallen als oneven getallen, dus de kans dat een getal even is danwel oneven is, is gelijk.

    Is het getal even dan wordt gedeeld door 2, is het getal oneven, dan keer 3 plus 1.
    Indien het even getal gedeeld is door 2, dan is de kans dat de uitkomst een even getal is even groot als een oneven getal. Immers van beide zijn er evenveel.
    Indien het oneven getal vermenigvuldigd is met 3 waarbij 1 wordt opgeteld, is het getal met 100% zekerheid een even getal. De volgende bewerking in de reeks is dan gedeeld door 2. Effectief wordt het oneven getal dus vermenigvuldigd met 3/2 + een restterm (1/2). Deze restterm is ondergeschikt bij herhaalde bewerking (grotere getallen), maar zorgt er wel voor dat de reeks werkt, met gehele getallen werkt. Deze term kan weer evengoed oneven zijn als even, er zijn er even veel van.
    Dus de bewerkingen zijn op te vatten als een herhaalde vermenigvuldiging met 3/2 of met 1/2.

    Omdat even en oneven getallen even vaak voorkomen is het aantal keren dat met 3/2 wordt vermenigvuldigd en met 1/2 wordt vermenigvuldigd, gelijk, als je maar genoeg keren de bewerking uitvoert. (vergelijk de gemiddelde waarde van de dobbelsteengooi). Dat betekent dat effectief, herhaaldelijk met 3/2 keer 1/2 wordt vermenigvuldigd, ofwel met 3/4. Iedereen snapt dat als je maar vaak genoeg herhaald om met 3/4 te vermenigvuldigen je bij 1 uitkomt. Over meerdere bewerkingen gezien convergeert het dus. Daarnaast is elk volgend getal in de reeks een geheel getal. Je komt dan uiteindelijk uit bij het kleinste gehele getal: 1.

    Bij het gooien van een dobbelsteen kan je hebben dat je een paar keer 6 gooit, achter elkaar, er kan dan twijfel ontstaan, maar je weet dat je op gemiddeld 3,5 uitkomt als je maar vaak genoeg gooit.
    Bij het vermoeden van Collatz kan het gebeuren dat je een paar keer -keer 3- (plus 1)-met -vervolgens -gedeeld-door-twee achter elkaar hebt. Effectief vermenigvuldig je dan een paar keer met 3/2, dus het getal wordt groter. Je dan gaat denken oei oei kom ik nog wel bij 1 terecht, ik ga nu de verkeerde kant op. Wees gerust, ga stug door u komt vanzelf uit bij 1, hierboven staat het bewijs.

    Mogelijk zie ik wat over het hoofd, of klopt het anderzins niet. Het verhaal is echter goed genoeg om tegenover een willekeurige leek stand te houden, zeker als je het met overtuiging brengt, vandaar dus Ja Duhh. Voldoende voor het doel: genante situaties voorkomen.
    Mocht het niet kloppen, dan tref je statistisch gezien zeker - na korte of lange tijd- een slimmerik die het bovenstaande ontkracht. Die geeft dan weer nieuwe inzichten en helpt je dan weer verder met de bewijsvoering.
    Het pakt dus altijd goed uit, dat is een zekerheid.

  20. Lex Boersma:

    ho twee foutjes zijn blijven staan bij het overnemen:

    - Na herhaald vermenigvuldigen met 3/4 wordt het getal kleiner. en in deze zin herhaalt met een t.:
    Iedereen snapt dat als je maar vaak genoeg herhaalt om met 3/4 te vermenigvuldigen het getal kleiner wordt.

    - en de titel ontbreekt:
    bewijs van vermoeden van Collatz: Ja Duhh

  21. Lex Boersma:

    bewijs van vermoeden van Collatz: Ja Duhh

    zo staat bij "laatste reacties" de titel ook nog goed in beeld

  22. Sander:

    @ Lex, de "bewijs"-methode die je hier gebruikt is "probabilistic heuristics". Dit maakt het vermoeden aannemelijk, maar bewijst het niet. Zie de engelstalige wikipedia pagina "Collatz conjecture", onder het kopje "A probabilistic heuristic", voor meer details.

  23. Lex Boersma:

    bewijs van Collatz ja duhhh 2.

    Oké. zie mijn eerder bericht:
    Inmiddels heeft mijn populaire uiteenzetting ertoe geleid dat genante situaties worden voorkomen, ik heb blijkbaar correct uitgelegd waarom het zo is, en in populair jargon het bewezen.
    Vervolgens kan ik tegen echte wiskundigen die zeggen "maar je bewijsmethode is probabilistic heuristics", bluffen, ja dat weet ik maar je snapt nu wel hoe het werkt ?

    Tegelijkertijd vraag ik me als leek af of het wel iets met probabilistiek te maken heeft.
    Volgens mij is het een zekerheid, en zit er niets toevalsafhankelijks aan. Zie bovenstaande bewijsvoering.
    Toevalsafhankelijkheid moet toch aan de orde zijn als je het over probabilistiek hebt ?
    Bij deze verdiepingsslag is het voorbeeld met de dobbelsteen, minder gelukkig, want wel toevalsafhankelijk en niet exact. Het gemiddelde wordt bij meer gooien niet precies 3,5 maar zal er juist ook altijd wat omheen zweven, terwijl Collatz altijd tot precies 1 leidt.

    Of moet het bewijs geleverd worden dat er evenveel even als oneven getallen zijn ?
    Of is het bewijs nu toch geleverd ?

    Of gaan we voor de volgende verdieping?

  24. Sander:

    @ Lex, beschouw eens een variatie, waarbij we bij een oneven n niet 3n+1, maar 3n-1 doen. Jouw methode gaat ook voor deze variatie op en we hebben dus bewezen dat we altijd op 1 uit komen (eenmaal bij 1 is ieder volgend getal ook 1). Begin nu eens voor de grap met bijvoorbeeld 5 of 17. Je ziet dan dat in deze variatie verschillende cycles te vinden zijn. Hetzelfde zou kunnen gebeuren in het originele probleem...

  25. Lex Boersma:

    niet doorwrocht maar even primair:
    bij de grote getallen is de +1 nodig om de even getallen te krijgen, dat kan ook de (3*) -1 zijn (om te convergeren).

    als je na het convergeren bij de kleine getallen bent uit gekomen is de +1 nodig om uit te komen. Althans: met kleine getallen kom je uit, dat is al bekend.

    en bedankt voor je reactie.

  26. Lex:

    @sander bedoel je een loop
    met jouw voorbeeld: startgetal 5 en reeks 3x-1 en /2 ? 5-14-7-20-10-5-14-7-20-10-5 enz

    begrijp ik dat je dus moet bewijzen dat er niet toevallig een (heel groot) getal is waardoor je zo'n loop krijgt als je herhaaldelijk 3X +1 na oneven getal en /2 na even getal doet ? Ga ik morgen eens over nadenken...

    Best wel boeiend dat vermoeden van Collatz, dus ik snap het probleem van Ionica niet zo, maar die zal wel met haar hoofd bij haar promotie zitten, succes !

  27. Rednas:

    Statistische redeneringen zijn allang onderzocht en feit is dat 0,75 * getal + 0,25 altijd naar omlaag gaat. Maar ook tot 1? Dat is de vraag. Bovendien is er altijd de kans dat we hiermee in het 5%-waarschijnlijksgebied zitten en dat 95% van de getallen (er zijn er oneindig veel) anders reageert. Dat is dus geen bewijs.

    De crux zit ‘m in de veronderstelling dat bijvoorbeeld 3 * 11 + 1 als uitkomst het getal 34 heeft. Dat is onjuist. De uitkomst is 11, 11, 11 en 1. Het schijngetal 34 (even) is slechts een aanwijzig (zo men wil een enzym of een katalysator) die aangeeft dat er door 2 moet worden gedeeld. Daarna ontstaan 11 en 6, niet tweemaal 17. Het gevolg is dat het getal 11 (dat zich had voorgedaan als 34) weer terug is, met een aanhangsel. Nu is de 6 dubbel. Die verlaagt zichzelf tot 3. De 3 moet weer omhoog, met als uitkomst 3, 3, 3 en 1. De katalysator 10 (even) zorgt ervoor dat de 3 weer zichzelf wordt, maar de rest 4 blijft over. Dat getal (even) wordt verlaagd tot 2, en vervolgens tot 1.

    De premisse van de Collatz-cyclus is dat elk getal slechts één keer kan voorkomen. Door de werking van Collatz-formule herleidt elk getal zich tot 1. Er komen dan wel veel enen, maar dat is inherent aan de werking van de Collatz-katalysator (+1) en bovendien is dit een aanwijzing voor de premisse dat elk getal slechts één keer kan voorkomen: elk getal is immers een veelvoud van 1.

    Welke wiskundige schrijft hiervoor een formule?

  28. Naomi:

    welk abbonemet is het voordeligst op termijn van 0 tot 1, 1 tot 2 en 2 tot 3 jaar als je een fanatieke sms'er bent?

    Als je weet dat je voor het abbonement van 10€ 6oo gratis sms'jes krijgt en voor het abbonement van 15€ 10 000 gratis sms'jes krijgt en de eerste 8 maanden 50% korting krijgt op het abbonement van 15€.
    Normaal tarief per sms: 12 cent.

    ideeën voor op te lossen: met functie, grafieken, intervallen, vraagstukken...

Plaats een reactie


Je kunt LaTeX gebruiken in je reactie.
Gelieve antwoorden op puzzels tussen [SPOILER] en [/SPOILER] te plaatsen.