Az A. 899. feladat (2025. február)

A. 899. A híres végtelen emeletes végtelen szállodának (amelyben az emeletek és minden emeleten a szobák is a pozitív egész számokkal vannak számozva) továbbra is nagyon jól megy a dolga, minden szobában pontosan egy vendég lakik. A szálloda minden emeletén le szeretné szőnyegezni a folyosót, amihez be is szerzett végtelen sok (természetesen a pozitív egész számokkal számozott), de sajnos csak véges hosszúságú szőnyeget. Minden vendéget megkérdeztek, hogy mely szőnyegek tetszenek neki, és mindenki le is adott egy végtelen listát azon szőnyegekről, amelyeket szívesen látna a saját emeletén. Tudjuk, hogy bármely két vendéghez, akik különböző emeleten laknak, csak véges sok olyan szőnyeg található, amely mindkettőjüknek tetszik. Mutassuk meg, hogy el lehet osztani a szőnyegeket az emeletek között úgy, hogy minden vendéghez csak véges sok olyan szőnyeg legyen, amely tetszik neki, de nem arra az emeletre került, ahol ő lakik.

Javasolta: Imolay András (Budapest)

(7 pont)

A beküldési határidő 2025. március 10-én LEJÁRT.

Soroljuk fel a vendégeket (ismert, hogy ez lehetséges: a pozitív egész számpárok megszámlálható sokan vannak), és minden olyan szőnyeget, amely legalább egy vendégnek tetszik, rakjunk annak a vendégnek az emeletére, aki a legelső a felsorolásban azok közül a vendégek közül, akiknek tetszik a szőnyeg. Azokat a szőnyegeket, amelyek senkinek sem tetszenek, bárhova rakhatjuk (mondjuk rakjuk az összeset az első emeletre).

Gondoljuk meg, hogy ez a szétosztás megfelel a feladat feltételeinek. Tekintsünk egy tetszőleges vendéget, hívjuk mondjuk Gábornak, és legyen $\displaystyle n$ az a szám, ahányadik Gábor a vendégek felsorolásában. Melyek azok a szőnyegek, amelyek tetszenek Gábornak, de nem az ő emeletére kerülnek? Azok, amelyek tetszenek egy kisebb sorszámú vendégnek is, aki nem ugyanazon az emeleten lakik, mint Gábor. Ám ilyen vendégből csak véges sok van, és mindegyiküknek csak véges sok olyan szőnyeg tetszik, ami Gábornak is, így összesen is csak véges sok olyan szőnyeg van, amely Gábornak is tetszik, de nem az ő emeletére kerül. Éppen ezt akartuk bizonyítani.

Megjegyzés: ugyanez a megoldás rekurzív módon is elmondható. Soroljuk fel a vendégeket. Azokat a szőnyegek, amelyek tetszenek az elsőként felsorolt vendégnek, helyezzük el az ő emeletén. Ezután az $\displaystyle n.$ lépésben helyezzük el az $\displaystyle n.$-ként felsorolt vendég emeletén azokat a szőnyegeket, amelyek tetszenek neki, és még nem lettek korábban elhelyezve. Mivel eddig csak véges sok lépést végeztünk el, és minden lépésben csak véges sok olyan szőnyeg lett elhelyezve, amely az $\displaystyle n$. embernek is tetszik, így összesen is csak véges sok olyan szőnyeg lett már korábban elhelyezve, amely az $\displaystyle n$. vendégnek is tetszik. Ezzel a rekurzív eljárással tehát a szőnyegeket a feladat feltételeinek megfelelően osztottuk szét.

Statisztika:

18 dolgozat érkezett.
7 pontot kapott:	Aravin Peter, Balla Ignác , Bodor Mátyás, Czanik Pál, Forrai Boldizsár, Holló Martin, Keresztély Zsófia, Kocsis 827 Péter, Morvai Várkony Albert, Sánta Gergely Péter, Szakács Ábel, Szaszkó Benedek, Varga Boldizsár, Virág Tóbiás, Vödrös Dániel László, Xiaoyi Mo.
0 pontot kapott:	1 versenyző.
Nem számítjuk a versenybe a születési dátum vagy a szülői nyilatkozat hiánya miatt:	1 dolgozat.

A KöMaL 2025. februári matematika feladatai