Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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:

Az A. 821. feladat értékelése még nem fejeződött be.


A KöMaL 2022. márciusi matematika feladatai