3n+1 probleem?

Opgave - NWO 2000 vraag 5

Een rij velden is genummerd $1,2,3,\ldots$. Een pion mag bij elke stap volgens een van de volgende regels van veld veranderen:
(i) van veld $n$ naar veld $2n$,
(ii) van veld $2n$ naar veld $n$,
(iii) van veld $n$ naar veld $3n+1$,
(iv) van veld $3n+1$ naar veld $n$.
a) Laat zien dat een pion van veld 29 naar veld 1 kan komen in een eindig aantal stappen.
b) Laat zien dat een pion van veld 63 naar veld 1 kan komen in een eindig aantal stappen.
c) Bewijs dat een pion van elk veld in de rij naar het veld met nummer 1 kan komen in een eindig aantal stappen.

Oplossing

We bewijzen dat je van elk getal naar elk ander getal kan overgaan in een eindig aantal stappen.

Van 0 kan je duidelijk naar 1 overgaan, van 1 duidelijk naar 2 enzovoorts.
Wanneer nu alle getallen $\leq a$ in elkaar kunnen overgaan, dan bewijzen we ook dat al deze getallen naar $a+1$ kunnen overgaan:
We onderscheiden 3 gevallen:
a+1 = 3n+1: a->n
a+1 = 3n+2: a -> 6n+4 -> 2n+1
a+1 = 3n: a -> 9n+1 -> 18n+2 -> 36n+4 -> 12n+1 -> 4n -> 2n
Darmee is inductief bewezen dat voor elk getal a+1 naar een getal, en dus ook alle getallen, kleiner of gelijk aan a kan overgegaan worden. Bijgevolg kan van elk natuurlijk getal naar elk ander natuurlijk getal overgegaan worden.

Da's inductie, je kunt het ook via een afdaling: met de methodes die je geeft kun je vanuit een getal > 0 altijd naar een strikt kleiner niet-negatief getal. Ooit kom je zo op 0 uit. Dus alle getallen kunnen naar 0, en omgekeerd kan 0 dus ook naar alle getallen.

Of extremaal: beschouw het kleinste getal van waaruit 1 of 0 niet bereikbaar is. Via je algoritme maken we een kleiner. :)