Az A. 835. feladat (2022. október)

A. 835. Jelölje \(\displaystyle f^{(n)}(x)\) az \(\displaystyle f\) függvény \(\displaystyle n\)-szeres iteráltját (azaz \(\displaystyle f^{(1)}(x)=f(x)\), \(\displaystyle f^{(n+1)}(x)=f\Big(f^{(n)}(x)\Big)\)).

Legyen \(\displaystyle p(n)\) egy adott egész együtthatós polinom, amely pozitív egész \(\displaystyle n\)-ekre pozitív egész értéket vesz föl. Lehet-e az \(\displaystyle f^{(n)}(n)=p(n)\) függvényegyenletnek pontosan egy \(\displaystyle f\colon \mathbb{Z}^+\to \mathbb{Z}^+\) függvény a megoldása?

Javasolta: Matolcsi Dávid és Szabó Kristóf (Budapest)

(7 pont)

A beküldési határidő 2022. november 10-én LEJÁRT.

Válasz: Semelyik polinomra sem pontosan egy megoldás létezik: minden polinomra vagy egyáltalán nem létezik megoldás, vagy végtelen sok megoldás van.

Ha \(\displaystyle p(x)=c\) konstans polinom, akkor végtelen sok megoldása van a függvényegyenletnek: minden \(\displaystyle f(n)=c\), kivéve \(\displaystyle f(2)\), ami egy tetszőleges \(\displaystyle c\)-től különböző pozitív egész.

Ha \(\displaystyle p(x)=x\), akkor is végtelen sok megoldás van: \(\displaystyle f(n)=n\) minden pozitív egész \(\displaystyle n\)-re, kivéve tetszőlegesen választott \(\displaystyle a\ne b\) páros számokra, amikre \(\displaystyle f(a)=b\) és \(\displaystyle f(b)=a\).

Ha \(\displaystyle p(x)=x+c\) alakú, ahol \(\displaystyle c\ge 1\), akkor belátjuk, hogy nincs megoldása a függvényegyenletnek.

Legyen \(\displaystyle g(k)=f^{(k)}(1)\). Ebben a sorozatban szerepelnek az \(\displaystyle 1, 1+c, 1+2c,...\) számok, így a sorozatnak minden eleme különböző kell, hogy legyen, különben a sorozat elemei hurokba érnének, és nem szerepelhetne végtelen sok különböző szám a sorozatban.

Mivel minden szám legfeljebb egyszer szerepel a \(\displaystyle g(k)\) sorozatban, ezért a sorozat csak véges sokszor vesz föl \(\displaystyle c+1\)-nél kisebb-egyenlő értéket, vagyis létezik olyan \(\displaystyle N\), hogy \(\displaystyle k>N\)-re \(\displaystyle g(k)>c+1\).

Vegyünk \(\displaystyle c+1\) egymást követő \(\displaystyle N\)-nél nagyobb sorszámú elemét a sorozatnak. Skatulyaelv szerint van köztük kettő, amik azonos maradékot adnak \(\displaystyle c\)-vel osztva, legyenek ők \(\displaystyle g(k)\) és \(\displaystyle g(m\)), ahol \(\displaystyle k<m\le k+c\).

Ha \(\displaystyle g(m)<g(k)\), akkor \(\displaystyle g(m+g(m))=g(m)+c\), aztán \(\displaystyle g(m+g(m)+g(g(m)))=g(m)+2c\), és így tovább. Mivel \(\displaystyle g(m)\) és \(\displaystyle g(k)\) azonos maradékot adnak \(\displaystyle c\)-vel osztva, így a sorozat valahol \(\displaystyle m\) után felveszi a \(\displaystyle g(k)\) értéket, ami ellentmondás azzal, hogy a sorozatban nem szerepelhet kétszer ugyanaz az érték.

Ha \(\displaystyle g(m)>g(k)\), akkor mivel \(\displaystyle g(k)>c+1\), ezért \(\displaystyle k+g(k)>m\), és \(\displaystyle k+g(k)+g(g(k))\) és az ezután következő elemek is értelemszerűen nagyobbak \(\displaystyle m\)-nél. Márpedig ezeken a helyeken a sorozat sorra felveszi a \(\displaystyle g(k)+c, g(k)+2c,...\) értékeket, így idővel a \(\displaystyle g(m)\) értéket is, ez megint ellentmondás, mert a sorozat nem veheti föl két különböző helyen ugyanazt az értéket.

Ezzel tehát beláttuk, hogy \(\displaystyle p(x)=x+c\) esetén nincs megoldás.

Ha \(\displaystyle p(x)\) nem \(\displaystyle x+c\) alakú, akkor belátjuk, hogy ha van megoldása a függvényegyenletnek, akkor végtelen sok megoldása van.

Tegyük föl, hogy létezik egy \(\displaystyle f_0\) megoldás. Könnyű látni, hogy pontosan azokra az \(\displaystyle n\)-ekre teljesül, hogy az \(\displaystyle f_0^{(k)}(n)\) sorozat többször is felveszi ugyanazt az elemet (hurokba ér), amikre a \(\displaystyle p^{(k)}(n)\) sorozat hurokba ér.

Készítünk egy új \(\displaystyle f\) függvényt. Azokhoz az \(\displaystyle n\)-ekhez, amikre \(\displaystyle p^{(k)}(n)\) hurokba ér, \(\displaystyle f\) rendelje ugyanazt, mint \(\displaystyle f_0\). Ilyen \(\displaystyle n\)-ből csak véges sok van, mert egy \(\displaystyle N\) korlát után a \(\displaystyle p\) polinom szigorúan monoton növő, és minden \(\displaystyle n\)-hez \(\displaystyle n\)-nél nagyobb számot rendel, így az már nem érhet hurokba. Ennek a véges sok számnak a halmazát \(\displaystyle H\)-nak nevezzük. Minden \(\displaystyle n\in H\)-ra teljesül \(\displaystyle f^{(n)}(n)=p(n)\), mivel ez teljesült \(\displaystyle f_0\)-ra.

Mivel a \(\displaystyle p\) polinom nem \(\displaystyle x+c\) alakú, ezért végtelen sok olyan pozitív egész van, amit nem vesz föl értékként, ezen nem fölvett számok közül nem \(\displaystyle H\)-beliből még mindig végtelen sok van, ezek halmazát \(\displaystyle A\)-nak nevezzük.

Mivel a \(\displaystyle p\) polinom egy korlát után szigorúan monoton növő és így injektív lesz, ezért csak véges sok olyan \(\displaystyle a\in A\) szám van, amire létezik \(\displaystyle b\in A\), amire létezik \(\displaystyle k\) és \(\displaystyle m\), hogy \(\displaystyle p^{(k)}(a)=p^{(m)}(b)\). Ez a véges sok szám alkotja a \(\displaystyle C\subset A\) halmazt.

Ha \(\displaystyle a\in C\), akkor legyen \(\displaystyle f(a)=f_0(a), f(f(a))=f_0(f_0(a)),...\) egészen addig az \(\displaystyle f^{(s)}(a)\)-ig, hogy minden \(\displaystyle b\in A\)-ra, amire létezik \(\displaystyle p^{(k)}(a)=p^{(m)}(b)\), arra \(\displaystyle f_0^{s}(a)\) megkapható \(\displaystyle f_0^{(r)}(b)\)-ként is. Ez mind a véges sok \(\displaystyle C\)-beli számra véges sok lépésben bekövetkezik, így ezzel még csak véges számra adtuk meg \(\displaystyle f\) értékét. \(\displaystyle D\)-nek nevezzük azon számok halmazát, amik itt értéket kaptak.

Ezután az alábbi algoritmus szerint adjuk meg \(\displaystyle f\) többi értékét:

Sorra végigmegyünk a pozitív egészeken. Ha a soron következő \(\displaystyle n\)-hez még nem rendelt értéket \(\displaystyle f\), akkor megnézzük, hogy létezik-e olyan \(\displaystyle m\), hogy \(\displaystyle f\) eddig lerögzített értékei szerint \(\displaystyle n=f^{(m-1)}(m)\). Ha igen (1.eset), akkor értelemszerűen legyen \(\displaystyle f(n)=p(m)\).

Ha nincsen ilyen \(\displaystyle m\) (2. eset), akkor legyen \(\displaystyle f(n)=r\), amire az alábbi tulajdonságok teljesülnek:

(I.) \(\displaystyle r\in A\setminus C,\)

(II.) \(\displaystyle r\) értéket még nem rendelte \(\displaystyle f\) semelyik számhoz,

(III.) \(\displaystyle r>p(N),\) ahol \(\displaystyle N\) az a korlát, ami után már a \(\displaystyle p\) polinom szigorúan monoton növő,

(IV.) Semmilyen \(\displaystyle a\)-ra, amihez már rendeltünk \(\displaystyle f\) szerinti értéket, és \(\displaystyle s\) számra nem teljesülhet, hogy

\(\displaystyle 1-\frac{1}{100K}<\frac{r}{p^{(s)}(a)}<1+\frac{1}{100K},\)

ahol \(\displaystyle K\) azon számoknak a száma, amikhez már rendeltünk korábban \(\displaystyle f\) szerinti értéket.

(V.) nem léteznek olyan \(\displaystyle a\) és \(\displaystyle t\) és \(\displaystyle i\) és \(\displaystyle j\) számok, amikre \(\displaystyle f^{(t)}(a)=n\) és

\(\displaystyle a+p(a)+p(p(a))...+p^{(i)}(a)=t+r+p(r)+...+p^{(j)}(r).\)

Belátjuk, hogy ha a 2. eset áll fönn, akkor mindig végtelen sok lehetséges \(\displaystyle r\) közül választhatunk. Ezt úgy látjuk be, hogy bemutatjuk, hogy kellően nagy \(\displaystyle R\)-re mindig található az összes feltételnek megfelelő \(\displaystyle r\) érték \(\displaystyle R\) és \(\displaystyle 2R\) között.

Mivel a \(\displaystyle p(x)\) polinom nem \(\displaystyle x+c\) alakú, ezért kellően nagy \(\displaystyle R\)-re legfeljebb az \(\displaystyle R\) és \(\displaystyle 2R\) közti számok felét veszi föl \(\displaystyle p\), a \(\displaystyle C\) halmaznak pedig csak véges sok eleme van, így \(\displaystyle R\) és \(\displaystyle 2R\) közt legalább a számok közel fele \(\displaystyle A\setminus C\)-ben van.

Minden \(\displaystyle a\)-ra, amihez már rendeltünk értéket, legfeljebb két \(\displaystyle p^{(s)}(a)\) érték van \(\displaystyle R\) és \(\displaystyle 2R\) között, így legfeljebb közel a számok \(\displaystyle \frac{1}{50}\) részére nem teljesül a (IV.) feltétel \(\displaystyle R\) és \(\displaystyle 2R\) között.

Vegyünk egy \(\displaystyle r\) számot, amire teljsesül az eslő négy feltétel. Ekkor egy tetszőleges \(\displaystyle a\)-ra, amihez már rendeltünk értéket létezik \(\displaystyle s\), hogy

\(\displaystyle (1+\frac{1}{100K})p^{(s)}(a)<r<(1-\frac{1}{100K})p^{(s+1)}(a).\)

Használva, hogy \(\displaystyle p(x)\) nem \(\displaystyle x+c\) alakú, teljesül, hogy

\(\displaystyle p^{(h)}(r)-p^{(s+h)}(a)>2^h(r-p^{(s)}(a))>2^h \frac{1}{100K} p^{(s)}(a).\)

Eközben

\(\displaystyle a+p(a)+...+p^{(s)}(a)<3p^{(s)}(a),\)

ezért ha \(\displaystyle k>\log_2(300K)\), akkor

\(\displaystyle t+b+p(b)+...+p^{(k)}(b)>a+p(a)+...+p^{(s+k)}(a).\)

Hasonlóan belátható, hogy ha \(\displaystyle k>\log_2(300K)\), akkor

\(\displaystyle t+b+p(b)+...+p^{(k)}(b)<a+p(a)+...+p^{(s+1+k)}(a).\)

Tehát minden \(\displaystyle a\)-ra csak a \(\displaystyle \log_2(300K)\)-nál kisebb \(\displaystyle i\) és \(\displaystyle j\) értékekre létezhet olyan, a (IV.) feltételt teljesítő \(\displaystyle r\), amire

\(\displaystyle a+p(a)+p(p(a))...+p^{(i)}(a)=t+r+p(r)+...+p^{(j)}(r),\)

és minden adott \(\displaystyle a\)-ra, \(\displaystyle i\)-re és \(\displaystyle j\)-re legfeljebb egy ilyen \(\displaystyle r\) létezik, mivel a \(\displaystyle t+r+p(r)+...+p^{(j)}(r)\) függvény szigorúan monoton növő.

Tehát az első négy feltételt teljesítő \(\displaystyle r\)-ek közül legfeljebb \(\displaystyle K\log_2^2(300K)\)-t zár ki az (V.) feltétel. Ez egy \(\displaystyle R\)-től nem függő konstans érték, így \(\displaystyle R\) és \(\displaystyle 2R\) közötti számok közül még mindig marad olyan, ami az összes feltételt teljesíti.

Most belátjuk, hogy legalább egyszer fennáll a 2. eset.

Indirekten tegyük föl ugyanis, hogy sosem áll elő a 2. eset. Ekkor egy kellően nagy \(\displaystyle M\)-re \(\displaystyle 1\)-től \(\displaystyle M\)-ig minden \(\displaystyle n\) szám az \(\displaystyle H\)-ban vagy \(\displaystyle D\)-ben van, vagy az 1. eset áll fenn rá, vagyis \(\displaystyle n=f^{(m-1)}(m)\), ahol \(\displaystyle m\le \frac{M}{2}\) vagy \(\displaystyle m\in D\), mert \(\displaystyle m>\frac{M}{2}\) esetén \(\displaystyle m\) és \(\displaystyle n\) között csak \(\displaystyle m-2\)-nél kevesebb számhoz rendeltünk értéket, így nem lehet \(\displaystyle n=f^{(m-1)}(m)\). Így azonban legfeljebb \(\displaystyle |H|+2|D|+\frac{M}{2}\) szám állhat elő, és ha \(\displaystyle M\) elég nagy, akkor ez kevesebb \(\displaystyle M\)-nél, tehát kell lennie olyan számnak \(\displaystyle 1\)-től \(\displaystyle M\)-ig, amire a 2. eset érvényesül.

Mivel beláttuk, hogy a 2. esetben végtelen sok függvényérték választható, ezért ezzel beláttuk, hogy ha a fentebb leírt algoritmus valóban helyes, akkor végtelen sok \(\displaystyle f\) megoldása van a függvéynegyenletnek.

Azt kell még belátnunk, hogy ha az 1. eset áll fönn, akkor mindig adható \(\displaystyle f(n)\)-nek érték egyértelmű módon. Ez pontosan akkor nem tehető meg, ha létezik két különböző \(\displaystyle m\) és \(\displaystyle k\), amikre \(\displaystyle n=f^{(m-1)}(m)\) és \(\displaystyle n=f^{(k-1)}(k)\), de \(\displaystyle p(m)\ne p(k)\).

\(\displaystyle m\)-re megvizsgáljuk, hogy ő már valaminek a képe volt-e \(\displaystyle f\) szerint, és ha igen, akkor az 1. eset szabálya szerint született-e. Ha igen, visszalépünk az \(\displaystyle m_1\) ősére, amire \(\displaystyle f^{(m_1)}(m_1)=p(m_1)=m\) volt. Ha \(\displaystyle m_1\) is az 1. eset szabálya szerint született, akkor ennek is visszalépünk így az ősére, amíg el nem érünk egy \(\displaystyle a\) számhoz, ami már nem az 1. eset szabálya szerint hozzárendelt \(\displaystyle f\) szerinti képe valaminek.

Abból, ahogyan \(\displaystyle a\)-t megkaptuk, következik, hogy

\(\displaystyle n=f^{(a+p(a)+...+p^{(i)}(a)-1)}(a)\)

egy \(\displaystyle i\ge 0\) értékre, ahol \(\displaystyle i=0\) annak felel meg, hogy \(\displaystyle a=m\).

Ugyanígy \(\displaystyle k\)-nak is megkeressük azt a \(\displaystyle b\) ősét, ami már nem az 1. eset szabálya szerint hozzárendelt \(\displaystyle f\) szerinti képe valaminek, és

\(\displaystyle n=f^{(b+p(b)+...+p^{(j)}(b)-1)}(b).\)

\(\displaystyle a\) és \(\displaystyle b\) értelemszerűen különbözőek, különben \(\displaystyle m\) és \(\displaystyle k\) sem lennének különbözőek.

Tegyük föl, hogy \(\displaystyle a\) és \(\displaystyle b\) egyike sem őse a másiknak (vagyis nem létezik \(\displaystyle t\), hogy \(\displaystyle f^{(t)}(a)=b\) vagy fordítva), de az \(\displaystyle n\) mégis közös leszármazottjuk, azaz \(\displaystyle f^{(q)}(a)=f^{(s)}(b)=n\) valamilyen \(\displaystyle s\) és \(\displaystyle q\) értékekre.

Ekkkor legyen \(\displaystyle n'\) az első közös leszármmazottjuk, és legyen \(\displaystyle a'\) és \(\displaystyle b'\) az \(\displaystyle a\)-nak és \(\displaystyle b\)-nek azon leszármazottjai, amikre \(\displaystyle f(a')=f(b')=n'\).

Ha \(\displaystyle f(a')\)-nek és \(\displaystyle f(b')\)-nek is a 2. eset szabálya szerint adtunk értéket, akkor amelyiknek később adtunk értéket, annak nem adhattunk volna olyan értéket, amit már hozzárendeltünk egy korábbihoz, tehát ekkor nem lehet \(\displaystyle f(a')=f(b')\).

Ha az egyikhez az 1., a másikhoz a 2. eset szabálya szerint rendelünk értéket, akkor az egyikhez rendelt érték \(\displaystyle A\)-beli, így nem veszi föl a \(\displaystyle p\) polinom, míg a másik \(\displaystyle p(m)\) alakú, így nem lehet \(\displaystyle f(a')=f(b')\).

Ha mind a kettő a 2. eset szerint kap értéket, akkor \(\displaystyle n'=f(a')=f(b')\) kétféleképpen is előáll \(\displaystyle p(s)\) alakban, ami azt jelenti, hogy \(\displaystyle n'\in D\), és az ősei is \(\displaystyle D\)-ben vannak, tehát \(\displaystyle a\in D\) és \(\displaystyle b\in D\).

Ekkor hozzájuk ugyanazt rendeli \(\displaystyle f\), mint \(\displaystyle f_0\), és a leszármazottaikhoz is, legalább az első pontig, amikor \(\displaystyle f_0^{(s)}(a)=f_0^{(r)}(b).\)

Mivel

\(\displaystyle f^{(a+p(a)+...+p^{(i)}(a)-1)}(a)=n=f^{(b+p(b)+...+p^{(j)}(b)-1)}(b),\)

ez azt jelenti, hogy \(\displaystyle s-r=(a+p(a)+...+p^{(i)}(a))-(b+p(b)+...+p^{(j)}(b)).\)

Ebből pedig az következik, hogy

\(\displaystyle p^{(i+1)}(a)=f_0^{(a+p(a)+...+p^{(i)}(a))}(a)=n=f_0^{(b+p(b)+...+p^{(j)}(b))}(b)=p^{(j+1)}(b).\)

Az \(\displaystyle f(n)\)-hez rendelendő két érték éppen \(\displaystyle p^{(i+1)}(a)\) és \(\displaystyle p^{(j+1)}(b)\), tehát mivel ezek egyenlőek, akkor mégis tudjuk követni az 1. eset szabályát.

Most már csak azt az esetet kell megvizsgálnunk, amikor \(\displaystyle a\) és \(\displaystyle b\) közül az egyik őse a másiknak, az általánosság rovása nélkül \(\displaystyle f^{(t+1)}(a)=b\).

Legyen \(\displaystyle f^{(t)}(a)=c\). Ha \(\displaystyle c\in D\), akkor \(\displaystyle a\in D\), és akkor az előző logika alapján az \(\displaystyle f(n)\)-hez rendelendő \(\displaystyle p^{(i+1)}(a)\) és \(\displaystyle p^{(j+1)}(b)\) értékek egyenlőek.

Tehát \(\displaystyle c\notin D\), tehát az 1. vagy 2. eset szabálya szerint rendeltük \(\displaystyle f(c)\)-hez a \(\displaystyle b\) értéket, és \(\displaystyle b\) definíciójánál feltettük, hogy nem az 1. eset volt érvényben.

Tehát a 2. eset szabálya szerint \(\displaystyle f(c)=b\) egy \(\displaystyle A\)-beli szám, amelyre az (V.) feltétel szerint semmilyen \(\displaystyle i\)-re és \(\displaystyle j\)-re nem teljesül, hogy

\(\displaystyle t+b+p(b)+...+p^{(j)}(b)=a+p(a)+...p^{(i)}(a).\)

Ez azonban ellentmond annak a feltevésünknek, hogy

\(\displaystyle n=f^{(b+p(b)+...+p^{(j)}(b)-1)}(b)=f^{(t+b+p(b)+...+p^{(j)}(b)-1)}(a)\)

és egyben

\(\displaystyle n=f^{(a+p(a)+...p^{(i)}(a)-1)}(a).\)

Ezzel ellentmodásra jutottunk, vagyis az 1. esetben mindig egyértelmű, hogy melyik értéket kell \(\displaystyle n\)-hez rendelni.

Tehát a megadott algortmus minden számhoz rendel értéket, és az 1. eset szabálya miatt a kapott \(\displaystyle f\)-re teljesül, hogy \(\displaystyle f^{(m)}(m)=p(m)\) minden pozitív egész \(\displaystyle m\)-re. Azt is beláttuk, hogy van olyan, amikor a 2. eset áll fönn, így végtelen sok választási lehetőségünk van az lagoritmus folytatásában, ez azt jelenti, hogy végtelen sok megoldása van a függvényegyenletnek.

Statisztika:

3 dolgozat érkezett.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2022. októberi matematika feladatai