 |
Az A. 821. feladat (2022. március) |
A. 821. \(\displaystyle a)\) Létezik-e olyan \(\displaystyle f\colon \mathbb{N}^2\to \mathbb{N}\) függvény, melyre minden \(\displaystyle g\colon \mathbb{N}\to \mathbb{N}\) függvény és \(\displaystyle m\) pozitív egész esetén létezik \(\displaystyle n \in \mathbb{N}\), melyre a \(\displaystyle \big\{k\in \mathbb{N} \colon f(n,k)=g(k)\big\}\) halmaz elemszáma legalább \(\displaystyle m\)?
\(\displaystyle b)\) Létezik-e olyan \(\displaystyle f\colon \mathbb{N}^2\to \mathbb{N}\) függvény, melyre minden \(\displaystyle g\colon \mathbb{N}\to \mathbb{N}\) függvény esetén létezik \(\displaystyle n \in \mathbb{N}\), melyre a \(\displaystyle \big\{k\in \mathbb{N} \colon f(n,k)=g(k)\big\}\) halmaz elemszáma végtelen?
(7 pont)
A beküldési határidő 2022. április 11-én LEJÁRT.
Megoldás. a)
Igen, létezik.
Legyen \(\displaystyle F_N\) azon \(\displaystyle f:\mathbb{N}\to \mathbb{N}\) függvények halmaza, amelyek a \(\displaystyle \{0,1,...,N\}\) helyek kivételével mindenütt \(\displaystyle 0\) értéket vesznek föl, és minden értékük legfeljebb \(\displaystyle N\).
Látható, hogy \(\displaystyle F_N\)-nek véges sok eleme van minden \(\displaystyle N\)-re, így felsorolhatóak egymás után először \(\displaystyle F_1\), aztán \(\displaystyle F_2, F_3, ...\) elemei, a teljes felsorolás tagjai együtt \(\displaystyle f_0, f_1, f_2,...\)
Legyen \(\displaystyle f(n,k)=f_n(k)\), belátjuk, hogy ez megfelel a feltételeknek.
Tetszőleges \(\displaystyle g:\mathbb{N}\to \mathbb{N}\) függvényre és \(\displaystyle m\in \mathbb{Z}^+\)-ra legyen \(\displaystyle N>m\) és \(\displaystyle N>\max\{g(0),g(1),...,g(m-1)\}\).
Ekkor \(\displaystyle F_N\)-ben szerepel egy olyan \(\displaystyle f\) függvény, amire \(\displaystyle f(0)=g(0), f(1)=g(1),...,f(m-1)=g(m-1)\).
Ez az \(\displaystyle f\) tehát szerepel az \(\displaystyle f_0, f_1,f_2,...\) felsorolásban is, tehát létezik olyan \(\displaystyle n\), amire \(\displaystyle g(0)=f(n,0), g(1)=f(n,1),...,g(m-1)=f(n,m-1)\),
vagyis amire \(\displaystyle \{k\in \mathbb{N}: f(n,k)=g(k)\}\) elemszáma legalább \(\displaystyle m\).
b)
Nem. Ezt a Cantor-féle átlós módszerhez hasonlóan bizonyítjuk:
Tegyük föl, hogy létezik ilyen \(\displaystyle f\). Ekkor létrehozunk egy \(\displaystyle g:\mathbb{N}\to \mathbb{N}\) függvényt, amire \(\displaystyle g(k)\ne f(n,k)\) semmilyen \(\displaystyle n\le k\)-ra. Ilyen \(\displaystyle g\) létezik, mert minden értékére csak véges sokat zártunk ki a felvehető végtelen sok természetes szám közül.
Erre a \(\displaystyle g\) függvényre tetszőleges \(\displaystyle n\in \mathbb{N}\)-re \(\displaystyle f(n,k)\ne g(k)\) ha \(\displaystyle k\ge n\), így \(\displaystyle f(n,k)=g(k)\) csak véges sok \(\displaystyle k\)-ra teljesülhet.
Tehát \(\displaystyle g\) ellenpélda arra a feltevésünkre, hogy létezne hozzá olyan \(\displaystyle n\), amire \(\displaystyle \{k\in \mathbb{N}: f(n,k)=g(k)\}\) elemszáma végtelen.
Statisztika:
12 dolgozat érkezett. 7 pontot kapott: Diaconescu Tashi, Kökényesi Márk Péter, Lovas Márton, Nádor Benedek, Tarján Bernát, Varga Boldizsár. 6 pontot kapott: Ben Gillott. 3 pontot kapott: 4 versenyző. 1 pontot kapott: 1 versenyző.
A KöMaL 2022. márciusi matematika feladatai