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

A B. 4803. feladat (2016. május)

B. 4803. Meg lehet-e adni a számegyenesen racionális végpontú zárt intervallumokat úgy, hogy minden racionális szám pontosan egy intervallum végpontja legyen, továbbá

\(\displaystyle a)\) bármelyik két zárt intervallum közül az egyik tartalmazza a másikat;

\(\displaystyle b)\) semelyik két intervallum nem diszjunkt és egyik sem tartalmazza a másikat?

Gáspár Merse Előd ötletéből

(6 pont)

A beküldési határidő 2016. június 10-én LEJÁRT.


Megoldás. a) A válasz igen. Ennek igazolásához mutatunk egy megfelelő konstrukciót. Álljon az intervallumrendszer az \(\displaystyle I_a=[-a,a]\) intervallumokból, ahol \(\displaystyle a\) nemnegatív racionális szám, speciálisan \(\displaystyle a=0\)-ra az egypontú \(\displaystyle [0,0]\) intervallumot kapjuk. Minden racionális szám pontosan az egyik intervallumnak végpontja: az \(\displaystyle r\) racionális szám esetén ez a \(\displaystyle [-|r|,|r|]\) intervallum. Az is teljesül, hogy bármelyik két intervallum közül az egyik tartalmazza a másikat, ha ugyanis \(\displaystyle 0\leq a<b\), akkor \(\displaystyle I_a\subseteq I_b\). Ezzel beláttuk, hogy a megadott rendszer kielégíti a feladat feltételeit.

b) Először egy olyan \(\displaystyle f:(-\infty,\sqrt{2})\cap\mathbb{Q}\to (\sqrt{2},\infty)\cap \mathbb{Q}\) bijekció létezését mutatjuk meg, amelyre teljesül, hogy tetszőleges \(\displaystyle a<b<\sqrt{2}\) racionális számokra \(\displaystyle \sqrt{2}<f(a)<f(b)\), vagyis \(\displaystyle f\) szigorúan monoton növekedő. Mivel a racionális számok halmaza megszámlálhatóan végtelen, ezért a racionális számok felsorolhatók egy \(\displaystyle q_1,q_2,\dots\) sorozat tagjaiként. Az \(\displaystyle f\) függvényt egy rekurzív eljárás segítségével határozzuk meg, melynek minden lépésében egyetlen új helyen írjuk elő \(\displaystyle f\) értékét. Tegyük fel, hogy \(\displaystyle f\) értékét már véges sok helyen megválasztottuk úgy, hogy a monotonitási feltétel teljesül. Legyen \(\displaystyle k\) a legkisebb olyan pozitív egész szám, amelyre \(\displaystyle q_k\)-nak még nincs párja, azaz \(\displaystyle q_k<\sqrt{2}\) esetén \(\displaystyle q_k\) képét még nem írtuk elő, \(\displaystyle \sqrt{2}<q_k\) esetén pedig \(\displaystyle q_k\) még nem kép. Tegyük fel, hogy \(\displaystyle f\) egyelőre az \(\displaystyle r_1<r_2<\dots <r_n<\sqrt{2}\) számokhoz rendel valamit úgy, hogy teljesül a monotonitási feltétel.

Tegyük fel először, hogy \(\displaystyle q_k<\sqrt{2}\). Ha valamely \(\displaystyle 1\leq i\leq n-1\)-re \(\displaystyle r_i<q_k<r_{i+1}\), akkor \(\displaystyle f(q_k)\) legyen egy tetszőleges racionális szám az \(\displaystyle (f(r_i),f(r_{i+1}))\) intervallumból. Ha \(\displaystyle q_k<r_1\), akkor \(\displaystyle f(q_k)\) legyen egy \(\displaystyle (\sqrt{2},f(r_1))\)-beli racionális szám. Végül, ha \(\displaystyle r_n<q_k<\sqrt{2}\), akkor legyen \(\displaystyle f(q_k)\) egy tetszőleges \(\displaystyle f(r_n)\)-nél nagyobb racionális szám. Minden nemüres nyílt intervallum tartalmaz racionális pontot, ezért az összes esetben találunk megfelelő \(\displaystyle f(q_k)\)-t, továbbá a konstrukció miatt az \(\displaystyle f\) függvény továbbra is kielégíti a monotonitási feltételt, speciálisan az is teljesül, hogy \(\displaystyle f\) injektív.

Most pedig tegyük fel, hogy \(\displaystyle \sqrt{2}<q_k\). Ha valamely \(\displaystyle 1\leq i\leq n-1\)-re \(\displaystyle f(r_i)<q_k<f(r_{i+1})\), akkor \(\displaystyle q_k\) legyen egy tetszőleges racionális szám (\(\displaystyle f\) szerinti) képe az \(\displaystyle (r_i,r_{i+1})\) intervallumból. Ha \(\displaystyle \sqrt{2}<q_k<f(r_1)\), akkor \(\displaystyle q_k\) legyen egy tetszőleges, \(\displaystyle r_1\)-nél kisebb racionális szám képe. Végül, ha \(\displaystyle r_n<q_k\), akkor \(\displaystyle q_k\) legyen egy tetszőleges, \(\displaystyle (r_n,\sqrt{2})\)-beli racionális szám képe. Minden nemüres nyílt intervallum tartalmaz racionális pontot, ezért az összes esetben találunk megfelelő ősképet, továbbá a konstrukció miatt az \(\displaystyle f\) függvény továbbra is kielégíti a monotonitási feltételt, speciálisan az is teljesül, hogy \(\displaystyle f\) injektív.

Ezt az eljárást folytatva végül (megszámlálhatóan végtelen sok lépés után) egy szigorúan monoton növekedő bijekciót kapunk a \(\displaystyle \sqrt{2}\)-nél kisebb, és a \(\displaystyle \sqrt{2}\)-nél nagyobb racionális számok halmaza között, hiszen minden racionális számra teljesül, hogy véges sok lépés után (a \(\displaystyle k\)-adik racionális szám esetén legfeljebb \(\displaystyle k\) lépés után) már előáll képként vagy ősképként. Azt állítjuk, hogy az \(\displaystyle (r,f(r))\) intervallumok (ahol \(\displaystyle r<\sqrt{2}\) racionális szám) megfelelő rendszert alkotnak. Mivel \(\displaystyle f\) bijekció \(\displaystyle \sqrt{2}\)-nél kisebb és a \(\displaystyle \sqrt{2}\)-nél nagyobb számok halmaza között, ezért minden racionális szám pontosan egy intervallumnak végpontja. Világos, hogy semelyik kettő metszete nem üres, hiszen a \(\displaystyle \sqrt{2}\)-t mind tartalmazzák. Továbbá, ha \(\displaystyle r<s<\sqrt{2}\), akkor \(\displaystyle \sqrt{2}<f(r)<f(s)\), vagyis egyik intervallum sem tartalmazhatja semelyik másikat. Ezzel beláttuk, hogy a feladat b) kérdésére is igen a válasz.

Megjegyzés. A feladat a) részében található olyan konstrukció is, amelyben nem szerepel egypontú intervallum, ehhez a b) rész megoldásához hasonlóan egy olyan bijekciót kell keresni például a \(\displaystyle (-\infty,\sqrt{2})\)-beli racionális számok és a \(\displaystyle (\sqrt{2},\infty)\)-beli racionális számok halmaza között, amelyik szigorúan monoton csökkenő.


Statisztika:

52 dolgozat érkezett.
6 pontot kapott:Andó Angelika, Baran Zsuzsanna, Borbényi Márton, Bukva Balázs, Gáspár Attila, Hansel Soma, Imolay András, Janzer Orsolya Lili, Kerekes Anna, Keresztfalvi Bálint, Klász Viktória, Kovács 246 Benedek, Kőrösi Ákos, Lajkó Kálmán, Lakatos Ádám, Matolcsi Dávid, Molnár-Sáska Zoltán, Nagy Nándor, Németh 123 Balázs, Tóth Viktor, Váli Benedek, Várkonyi Dorka, Zólomy Kristóf.
5 pontot kapott:Busa 423 Máté, Nagy Kartal, Saár Patrik, Varga-Umbrich Eszter.
4 pontot kapott:1 versenyző.
3 pontot kapott:1 versenyző.
2 pontot kapott:11 versenyző.
1 pontot kapott:4 versenyző.
0 pontot kapott:6 versenyző.
Nem versenyszerű:2 dolgozat.

A KöMaL 2016. májusi matematika feladatai