Fórum: Érdekes matekfeladatok

10-es számrendszerben összesen 109 fixpont van, éspedig:

22,10213223,10311233,10313314,10313315,10313316,10313317,10313318,10313319,21322314, 21322315,21322316,21322317,21322318,21322319,31123314,31123315,31123316,31123317,31123318, 31123319,31331415,31331416,31331417,31331418,31331419,31331516,31331517,31331518,31331519, 31331617,31331618,31331619,31331718,31331719,31331819,1031223314,1031223315,1031223316, 1031223317,1031223318,1031223319,3122331415,3122331416,3122331417,3122331418,3122331419, 3122331516,3122331517,3122331518,3122331519,3122331617,3122331618,3122331619,3122331718, 3122331719,3122331819,10413223241516,10413223241517,10413223241518,10413223241519, 10413223241617,10413223241618,10413223241619,10413223241718,10413223241719,10413223241819, 41322324151617,41322324151618,41322324151619,41322324151718,41322324151719,41322324151819, 41322324161718,41322324161719,41322324161819,41322324171819,1051322314251617, 1051322314251618,1051322314251619,1051322314251718,1051322314251719,1051322314251819, 1051322325161718,1051322325161719,1051322325161819,1051322325171819,5132231425161718, 5132231425161719,5132231425161819,5132231425171819,5132232516171819,106132231415261718, 106132231415261719,106132231415261819,106132231426171819,106132231526171819, 613223141526171819,1011112131415161718,1011112131415161719,1011112131415161819, 1011112131415171819,1011112131416171819,1011112131516171819,1011112141516171819, 1011113141516171819,1111213141516171819,10713223141516271819,101112213141516171819

Ezzel kapcsolatban érdekes volt megfigyelni azt, hogy a legkisebb fixpontok minden számrendszerben csupa egyforma számjegyből állnak. (Vajon ezt a tényt külön be lehetne/lehetett volna látni a konkrét értékek ismerete nélkül?)

Kicsit átírtam a progit, hogy más számrendszerekkel is menjen. Ezeket találtam a kül. számrendszerekre:

2-es: 111, 1101001

3-as: 22, 10111, 11112, 100101, 2021102, 1011122, 10010122

4-es: 22, 1011112, 1011113, 1111213, 10213223, 10311233, 101112213

5-ös: 22, 10213223, 10311233, 10313314, 21322314, 31123314, 101111x1y (1<x<y), 10111221314

Elvileg ezekre nincs is más megoldás.

10-esre ezek a legfeljebb 8-jegyű megoldások, itt is csak pár sorozat van (3<x<y): 22, 10213223, 10311233, 1031331x, 2132231x, 3112331x, 31331x1y

És ugye igaz, hogy ha van olyan megoldás, ahol minden darabszám egyjegyű, akkor az minden magasabb számrendszerben is megoldás lesz.

Nem írtam át a progit a 2-es számrendszer kezelésére (amúgy is csak otthon van meg, ezt meg a villamoson agyaltam reggel fejben). De akkor kicsit kipofozom majd.

Érdekes, azt gondoltam, hogy a kettes számrendszerbeli kis megoldásokat számítógéppel könnyen megtalálod. Van pontosan egy kisebb is a 1101001-nél.

Ez a C függvény más számrendszerek esetén is érdekes lehet. Pl. 2-es számrendszernél szenvedtem egy kicsit, mire összehoztam a 1101001 számot (tudtok még?). Itt ugyanis nem megy a 22, mint legkisebb megoldás, ami minden más számrendszernél működik.

Igen, pont erre én is rátaláltam véletlenül, és 5 perc kísérletezés után sem találtam nagyobbat :)

Egy nagy fixpont például a 101112213141516171819. Azt nem mondom, hogy nincs ennél is nagyobb.

A C függvényről szóló 6. feladat nem nehéz. Könnyű látni, hogy ha n legfeljebb 10ⁿ jegyből áll, akkor C(n) legfeljebb 10(n+1) jegyből. Így aztán 30 jegyűnél hosszabb fixpont nem létezhet, tehát kell lennie legnagyobb fixpontnak. Ugyanez részben megoldja az 5. feladatot is, ugyanis azt bizonyítja, hogy minden számból indulva előbb-utóbb olyan ciklusba esünk, amiben minden elem legfeljebb 10¹⁰³⁰, így a ciklus is legfeljebb ilyen hosszú. Hasonlóan viszont azt is könnyű látni, hogy van tetszőlegesen hosszú átmeneti szakasz, mert ha n legalább 10^.10ⁿ jegyű, akkor C(n) legalább 1+n jegyű (vagy valami hasonló egyenlőtlenség igaz).

A 3. és 4. feladatot feltehetően kimerítő kereséssel meg lehet válaszolni, kivéve ha valamiért nincsen 2-es ciklus, vagy a legkisebb is nagyon nagy.

Következzen végül néhány újabb kérdés és sejtés a C függvény kapcsán, amelyek természetes módon felmerülnek és amelyek között szerintem nehezebbek is vannak. (A saját tippjeimet egyelőre nem írom ide, hogy ne befolyásoljak senkit.)

Egy n szám 2-es ciklus, ha C(n)n, de C(C(n))=n. Hasonlóan definálhatók a k-hosszú ciklusok is.

3. feladat. Melyik az a legkisebb n, amely (a C leképezés iterációja során) előbb-utóbb 2-es ciklust eredményez?

4. feladat. Melyik az a legkisebb n, amely rögtön egy 2-es ciklus egyik tagja?

5. feladat. Igaz-e, hogy minden kezdőértékre a C iteráltjaiból alkotott sorozat előbb-utóbb ciklikussá válik? Ha igen, van-e tetszőlegesen hosszú "átmeneti szakasz", mielőtt a sorozat ciklizálni kezd? Van-e maximális ciklushossz, vagy pedig tetszőlegesen hosszú ciklusok előfordulhatnak?

6. feladat. Igaz-e, hogy C-nek van legnagyobb fixpontja? Ha igen, konkrétan melyik szám az?

A fenti C leképezést egyébként a Conway-féle "look and say" sorozat mintájára gyártottam, csak annál egyszerűbb. A Conway-féle sorozat sok érdekes tulajdonsággal bír, különösen meghökkentő a rá vonatkozó "cosmological theorem".