hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu en hu hu hu hu hu en hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu en en en hu sk hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu de hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu hu en ar bn ca hbs_lat da de el eo es eu fa fi fr he hi tl is it ja ko fr nl nb pl pt ru en sl sv tr fy vi zh zh zh hu hu hu hu hu hu hu hu hu hu
A Wikipédiából, a szabad enciklopédiából
Ez a közzétett változat, ellenőrizve: 2022. szeptember 26.
Ugrás a navigációhoz Ugrás a kereséshez
Vajon a Collatz-sorozat eléri-e az 1 értéket minden pozitív egész kiindulási érték esetén?
(A matematika további megoldatlan problémái)
A Collatz-sejtés egy máig megoldatlan probléma a matematikában. Több más néven is ismert, például Ulam-sejtés vagy 3n+1 probléma. A sejtés a nevét Lothar Collatzról kapta, aki 1937-ben fogalmazta meg azt.
A probléma a következő: Tetszőleges pozitív egész számból kiindulva képezzünk végtelen sorozatot úgy, hogy ha a sorozat utoljára kiszámított eleme páros, akkor a rákövetkező elem ennek fele lesz, különben viszont a háromszorosánál eggyel nagyobb szám. Például ha a 7-ből indulunk ki (amely páratlan), akkor a rákövetkező elem 3 ⋅ 7 + 1 = 22 {\displaystyle 3\cdot 7+1=22} , amely páros, így a következő elem a 22 fele, azaz 11 lesz. Tovább folytatva a szabály alkalmazását a 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, ... sorozatot kapjuk. Látható, hogy innentől a végtelenségig ismétlődik a 4, 2, 1 számhármas. Különböző számokból kiindulva azt tapasztaljuk, hogy újra meg újra olyan sorozatokat kapunk, amelyek a 4, 2, 1 számhármas végtelen ismétlődésébe torkollnak. A Collatz-sejtés azt mondja ki, hogy ez mindig így van: akármilyen pozitív számmal is kezdjük a sorozat képzését, a végén mindig a 4, 2, 1 ciklusba futunk bele. Egyelőre megoldatlan probléma annak eldöntése, hogy a sejtés helyes-e.[1]
Legyen a 0 {\displaystyle a_{0}} egy tetszőleges pozitív egész szám. A sorozat szabálya a következő:
a n + 1 = { a n 2 , ha  a n  páros 3 a n + 1 , ha  a n  páratlan {\displaystyle a_{n+1}={\begin{cases}{\frac {a_{n}}{2}}{\text{, ha }}a_{n}{\text{ páros}}\\3a_{n}+1{\text{, ha }}a_{n}{\text{ páratlan}}\end{cases}}}
A sejtés szerint a sorozat egy a 0 {\displaystyle a_{0}} -tól függő n {\displaystyle n} értéktől kezdve ugyanazt a ciklust fogja ismételni minden kiindulási érték esetén: 1 , 4 , 2 {\displaystyle 1,4,2} . Azt a legkisebb számot, amitől kezdve ismétlődik a sorozat, megállási időnek nevezzük. Így a sejtés átfogalmazható: A fenti rekurziós képlet esetén minden a 0 {\displaystyle a_{0}} -ra van megállási idő.
Ha a sejtés hamis, akkor két lehetőségünk van:
a sorozat olyan ciklusba fut bele, ami nem tartalmazza az 1-et;
a sorozat minden határon túl növekszik.
a 0 = 20 {\displaystyle a_{0}=20} esetén a sorozat: 20 , 10 , 5 , 16 , 8 , 4 , 2 , 1 , . . . {\displaystyle 20,10,5,16,8,4,2,1,...}
a 0 = 23 {\displaystyle a_{0}=23} esetén a sorozat kissé hosszabb: 23 , 70 , 35 , 106 , 53 , 160 , 80 , 40 , 20 , 10 , 5 , 16 , 8 , 4 , 2 , 1 {\displaystyle 23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1} , és, mint látható, egészen 160-ig növekszik.
Ha az indulási szám 2-hatvány, a sorozat megállási ideje kicsi lesz, egészen pontosan l o g 2 a 0 {\displaystyle log_{2}a_{0}} , mivel csak a felezési iteráció történik meg. Ellenben Mersenne-prímek esetén először n {\displaystyle n} alkalommal növekedni fog a sorozat M n {\displaystyle M_{n}} -ről indulva, mielőtt csökkenne.
A ciklusok olyan szám-n-esek, amelyek periodikusan ismétlődnek. A ( 4 , 2 , 1 ) {\displaystyle (4,2,1)} ciklus triviális, a sejtés szerint minden sorozat tartalmazza.
A pontos definíció szerint a 0 {\displaystyle a_{0}} -ból kiindulva az n-ciklus azt jelenti, hogy a n = a 0 {\displaystyle a_{n}=a_{0}} . Ha van ilyen ciklus, akkor a sejtés hamis.
A "rövidített" definíciója a ciklusoknak a következő:
a n + 1 = { a n 2 , ha  n  páros 3 a n + 1 2  egyébként {\displaystyle a_{n+1}={\begin{cases}{\frac {a_{n}}{2}}{\text{, ha }}n{\text{ páros}}\\{\frac {3a_{n}+1}{2}}{\text{ egyébként}}\end{cases}}}
Páratlan szám után ugyanis mindig páros következik. Így a ciklusokat a következőképpen jelölhetjük: ( a 0 , a 1 , a 2 , . . , a n − 1 ) {\displaystyle (a_{0},a_{1},a_{2},..,a_{n-1})} , mivel a n = a 0 {\displaystyle a_{n}=a_{0}} .
Ebben az esetben k {\displaystyle k} növekedés után ugyanennyi csökkenés következik be, ezt k-ciklusnak nevezzük. A triviális ciklus az ( 1 , 2 ) {\displaystyle (1,2)} , ezt 1-ciklusnak nevezzük. Ez az egyetlen ismert ciklus, így a sejtés másik formája. 1977-ben Steiner igazolta, hogy kizárólag ez az 1-ciklus létezik. A bizonyítást felhasználva Simons igazolta 2000-ben, hogy nincs 2-ciklus. 2003-ban Simons és de Weger igazolta, hogy nincsen k-ciklus, ha k ≤ 68 {\displaystyle k\leq 68} .
A legtöbb matematikus szerint a sejtés igaz, erre utalnak a kísérleti vizsgálatok.
Számítógépes módszerekkel a sejtést igazolták minden n ≤ 5 ⋅ 2 60 {\displaystyle n\leq 5\cdot 2^{60}} egészre. Ez magában nem jelenti a sejtés valószínűségének növekedését, mivel csak véges sok esetet lehet megvizsgálni a végtelen sokból. Előfordulhat ugyanis, hogy extrém nagy számok esetén találnak ellenpéldát, mint az történt például a Pólya-sejtés esetén. Éppen ezért a kérdést a kísérleti tapasztalatok nem támasztják alá megnyugtató módon.
Ha csak a páratlan számokat vizsgáljuk a sorozatban, az egymást követő számok hányadosa körülbelül 3/4. Ez arra utal. hogy a sorozat egy idő után csökkenni kezd. Természetesen mindez csak a divergenciát cáfolja, a sejtést nem igazolja. Ez alapján annyit lehet mondani, hogy a sejtés igazolódásának valószínűsége 1 bármely számra, ami nem jelenti azt, hogy minden számra igaz. (Ez egyszerűen a valószínűség tulajdonságaiból fakad.)
Bár szigorúan nem sikerült még belátni minden számra, hogy igaz rá a sejtés, igen sokra teljesül. Krasikov és Lagarias igazolta, hogy az [ 1 , x ] {\displaystyle \left[1,x\right]} intervallumban az ilyen számok mennyisége arányos x 0 , 84 {\displaystyle x^{0,84}} -nal.[2]
Collatz maga nagyon nehéznek ítélte a problémát, azért sokáig nem is publikálta, csak az ismerőseinek beszélt róla. Már 1929-ben részt vett Göttingenben többek között gráfokat is említő előadásokon, és a 30-as években megfogalmazott kérdéseket, de csak az ötvenes évekből említik, hogy a konkrét sejtést szóban emlegette más matematikusoknak, és az első publikációk csak az 1970-es évek elején születtek meg.[2]
Erdős Pál "teljesen reménytelen" problémának vélte. Ez nem akadályozta meg abban, hogy 500 dolláros díjat írjon ki a bizonyításáért.
B. Thwaites 1000 dollárt ajánlott fel a probléma megoldásáért.[3]
John Horton Conway bebizonyította, hogy a sejtés általánosítása algoritmikusan eldönthetetlen probléma.[4]
Shizuo Kakutani megemlékezik egy viccről, ami szerint a Collatz-sejtést azért találták ki, hogy lelassítsák az amerikai matematikai haladást. Erre példának hozta fel, hogy egyszer egy teljes hónapig a Yale egyetem minden matematikusa a sejtést próbálta bizonyítani.
↑ Eric W. Weisstein írása a MathWorld oldalon
↑ a b "Jeffrey C. Lagarias". „"The 3x+1 Problem: An Overview"”.
↑ Thwaites, B. "Two Conjectures, or How to Win £1100." Math. Gaz. 80, 35-36, 1996.
↑ Conway, J. H. "Unpredictable Iterations." Proc. 1972 Number Th. Conf., University of Colorado, Boulder, Colorado, pp. 49-52, 1972.
A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Collatz-sejtés&oldid=25310925”
Hivatkozás erre a változatra
Hogyan hivatkozz erre a lapra?
A lap utolsó módosítása: 2022. szeptember 26., 17:18
A lap szövege Creative Commons Nevezd meg! – Így add tovább! 3.0 licenc alatt van; egyes esetekben más módon is felhasználható. Részletekért lásd a felhasználási feltételeket.