A B. 4095. feladat (2008. május)

B. 4095. Adott a térbeli derékszögű koordinátarendszerben végtelen sok olyan tengelypárhuzamos téglatest, amelyek egyik csúcsa az origó, és minden csúcs koordinátái nemnegatív egész számok. Kiválasztható-e biztosan közülük kettő, amelyek közül az egyik tartalmazza a másikat?

Javasolta: Maga Péter

(5 pont)

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

Megoldás: Azt állítjuk, hogy egy egész végtelen sorozatot ki lehet választani úgy, hogy közülük bármelyik tartalmazza az összes megelőzőt. Ennek bizonyítása az alábbi észrevételen múlik: nemnegatív egész számok egy tetszőleges $k_1,k_2,\ldots$ sorozatából kiválasztható egy $k_{i_1},k_{i_2},\ldots$ részsorozat úgy, hogy $k_1\le k_2\le \ldots$ teljesüljön. Ha a sorozatban van végtelen sok megegyező elem, akkor ez nyilvánvaló. Egyébként tegyük fel, hogy már kiválasztottunk egy véges $k_{i_1}, k_{i_2},\ldots, k_{i_n}$ részsorozatot úgy, hogy $k_{i_1}< k_{i_2}<\ldots< k_{i_n}$ . Mivel feltevésünk értelmében a $k_{i_{n}+1},k_{i_{n}+2},\ldots$ számok között csak véges sok olyan lehet, amelyik nem nagyobb k_{i_n}-nél, léteznie kell olyan i_n+1>i_n indexnek, amelyre k_{i_n+1}>k_{i_n}, vagyis a részsorozat folytatható.

Legyenek most adva $T_1,T_2,\ldots$ tengelypárhuzamos téglatestek, amelyek egyik csúcsa az origó, és minden csúcs koordinátái nemnegatív egész számok. A T_i téglatest egyértelműen megadható az origóval szemközti csúcsával, melynek koordinátái legyenek (x_i,y_i,z_i). Itt x_i,y_i,z_i tehát nemnegatív egész számok. T_i pontosan akkor tartalmazza T_j-t, ha x_i $\ge$ x_j, y_i $\ge$ y_j és z_i $\ge$ z_j egyszerre teljesül. A fenti észrevétel értelmében létezik egy olyan $a_1<a_2<\ldots$ indexsorozat, melyre $x_{a_1}\le x_{a_2}\ldots$ teljesül. Ebből az indexsorozatból kiválasztható egy olyan $b_1<b_2<\ldots$ indexsorozat, amelyre $y_{b_1}\le y_{b_2}\le \ldots$ is teljesül. Végül ebből kiválaszthatunk egy $c_1<c_2<\ldots$ indexsorozatot, amelyre $z_{c_1}\le z_{c_2}\le\ldots$ is fennáll. Ekkor pedig a téglák $T_{c_1},T_{c_2},\ldots$ részsorozatára teljesülni fog bármely i<j esetén, hogy x_{c_i} $\le$ x_{c_j}, y_{c_i} $\le$ y_{c_j} és z_{c_i} $\le$ z_{c_j}, vagyis a T_{c_j} téglatest tartalmazza a T_{c_i} téglát.

Statisztika:

56 dolgozat érkezett.

5 pontot kapott: Aczél Gergely, Ágoston Tamás, Aujeszky Tamás, Bálint Dániel, Bencs 111 Ferenc, Blázsik Zoltán, Bodor Bertalan, Cséke Balázs, Deák Zsolt, Dinh Hoangthanh Attila, Dudás 002 Zsolt, Éles András, Énekes Péter, Farkas Márton, Fonyó Dávid, Frankl Nóra, Gévay Gábor, Gőgös Balázs, Grósz Dániel, Hursán Zsófia, Keresztfalvi Tibor, Kiss 243 Réka, Kiss 902 Melinda Flóra, Kovács 999 Noémi, Márkus Bence, Mészáros András, Nagy 648 Donát, Orosz Ákos, Perjési Gábor, Prok Tamás, Réti Dávid, Somogyi Ákos, Szabó 895 Dávid, Szalkai Balázs, Tossenberger Anna, Tóth 369 László Márton, Varga 171 László, Véges Márton, Zieger Milán.

4 pontot kapott: Wang Daqian.

3 pontot kapott: 1 versenyző.

2 pontot kapott: 2 versenyző.

1 pontot kapott: 2 versenyző.

0 pontot kapott: 11 versenyző.

A KöMaL 2008. májusi matematika feladatai

56 dolgozat érkezett.
5 pontot kapott:	Aczél Gergely, Ágoston Tamás, Aujeszky Tamás, Bálint Dániel, Bencs 111 Ferenc, Blázsik Zoltán, Bodor Bertalan, Cséke Balázs, Deák Zsolt, Dinh Hoangthanh Attila, Dudás 002 Zsolt, Éles András, Énekes Péter, Farkas Márton, Fonyó Dávid, Frankl Nóra, Gévay Gábor, Gőgös Balázs, Grósz Dániel, Hursán Zsófia, Keresztfalvi Tibor, Kiss 243 Réka, Kiss 902 Melinda Flóra, Kovács 999 Noémi, Márkus Bence, Mészáros András, Nagy 648 Donát, Orosz Ákos, Perjési Gábor, Prok Tamás, Réti Dávid, Somogyi Ákos, Szabó 895 Dávid, Szalkai Balázs, Tossenberger Anna, Tóth 369 László Márton, Varga 171 László, Véges Márton, Zieger Milán.
4 pontot kapott:	Wang Daqian.
3 pontot kapott:	1 versenyző.
2 pontot kapott:	2 versenyző.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	11 versenyző.

Már regisztráltál?
Új vendég vagy?