Kurusa Árpád

Matek-blog

A legegyszerűbb eldöntetlen probléma

Ha tud valaki egyszerűbbet, akkor értesítsen!

Vegyük a következő függvényt a természetes számok halmazán: $$ f\colon\Bbb N\to\Bbb N\qquad k\mapsto f(k)=\cases{k/2 & \hbox{ha $k$ páros},\\ 3k+1 & \hbox{ha $k$ páratlan}.} $$

Ezzel a függvénnyel és egy $a_0\in\Bbb N$ természetes számmal képezzük az $a_{j+1}=f(a_j)$ (rekurzív) sorozatot.

E sorozat egyetlen tagja sem lehet negatív semmilyen induló $a_0$ érték esetén, ezért van legkisebb értékű eleme. .

Mi egy ilyen sorozat legkisebb értéke? .

Néhány esetben könnyű látni, hogy a keresett minimum az 1.

Ezt mutatja az alábbi ábrázolás is az $a_0=$ kezdeti értékkel. Más induló értékre is kipróbálható ez, ha ebbe a mezőbe beírjuk és lenyomjuk az "enter"-t.

Ezen tapasztalat alapján született a sejtés, hogy

E sorozat minimuma minden kezdőérték esetén 1! .

Ha ez igaz, akkor az azt jelenti, hogy véges sok lépés után minden ilyen sorozat a végtelen $4,2,1,4,2,1,....$ ciklusba megy.

A most megfogalmazott probléma Collatz-sejtés néven ismert, eleddig megoldatlan.


Néhányan jelezték, hogy talán a $\pi^e$ racionalitásának problémája egyszerűbb, de szerintem már az $e$ és $\pi$ megértése is bonyolultabb, mint a fenti kérdés.


© 2014 Kurusa Árpád