Tag archieven: recursie

Het 3n+1 vermoeden

Geplaatst op door

Neem een natuurlijk getal n. Als het even is, deel het door 2. Als het oneven is, vermenigvuldig je het met 3 en tel er 1 bij op. Met de uitkomst doe je hetzelfde, en dat blijf je maar herhalen.

Neem bijvoorbeeld 6, dan ontstaat volgende rij : 6,3,10,5,16,8,4,2,1. We noemen dit de Collatz rij van 6. De lengte van deze Collatz rij is 9. De lengte van dergelijke rij kan snel oplopen. Zo is de lengte van de  Collatz rij van 27 gelijk aan 111.

Het 3n + 1-vermoeden zegt dat bovengenoemd iteratieproces bij iedere mogelijke startwaarde altijd een keer bij 1 zal uitkomen. De precieze oorsprong van het 3n + 1- vermoeden is niet helemaal duidelijk. In de jaren dertig was Lothar Collatz( 1910-1990), een Duitse wiskundige, met soortgelijke problemen bezig, en het 3n + 1-probleem wordt algemeen aan hem toegeschreven. Het is tot op heden nog steeds niet bewezen.

Er zijn enkele aanwijzingen dat het vermoeden van Collatz juist is. Voor alle getallen onder 10^{19}   is inmiddels gecontroleerd dat ze aan het vermoeden voldoen. Het probleem met het controleren is dat het alleen het vermoeden kan weerleggen. Als het vermoeden waar is, kan er geen bewijs voor gevonden worden op deze manier.

Recursie

Geplaatst op door

Een rij van getallen kan je geven met behulp van een recursief  voorschrift zoals bijvoorbeeld : a_1=1 en a_n= 2a_{n-1}+1. Soms kan je uit dit recursief voorschrift een expliciete formule afleiden voor de algemene term van de rij. Soms kan dat niet, maar is het mogelijk, via recursie, de parameters te herleiden tot waarden waarvoor je het probleem wel kan oplossen.

Een eerlijk muntstuk wordt n keer opgeworpen. Wat is de kans op twee opeenvolgende keren kop ergens in de rij worpen?

  • Noteer met P_n de kans dat er nergens twee keer kop na elkaar voorkomt is de rij van n worpen.
  • Het is duidelijk dat P_1=1 en P_2=\frac{3}{4}.
  • Stel n>2. Dan zijn er twee mogelijkheden naargelang de eerste worp kop of munt is.
  • Als je eerst munt gooit, dan is de kans dat je nergens twee keer kop na elkaar hebt in de volgende n-1 worpen gelijk aan P_{n-1}.
  • Gooi je eerst kop, dan moet de tweede worp munt zijn, want anders zou je twee keer kop na elkaar hebben. De kans dat je nergens twee keer kop na elkaar hebt in de volgende n-2 worpen gelijk aan P_{n-2}.
  • Uit de vorige twee punten vinden we tenslotte dat

        \[P_n=\frac{1}{2}P_{n-1}+\frac{1}{4}P_{n-2}\]

  • Dit kan je herleiden tot 2^nP_n=2^{n-1}}P_{n-1}+2^{n-2}P_{n-2}. Of via S_n=2^nP_n:

        \[S_n=S_{n-1}+S_{n-2}\]

  • Dit is de rij van Fibonacci, waarbij S_n het n+2 de getal in de rij van Fibonacci is. Dus S_n=F_{n+2}. De gezochte kans op twee opeenvolgende keren kop ergens in de rij van n worpen, met n>2 is dan X=1-P_n=1-\frac{F_{n+2}}{2^n}.