Problem B. 4095. (May 2008)
B. 4095. Given infinitely many cuboids with edges parallel to the axes of the coordinate space, one vertex at the origin and all vertices at points of non-negative integer coordinates. Is it always possible to select two, one of which contains the other?
Javasolta: P. Maga
(5 pont)
Deadline expired on June 16, 2008.
Sorry, the solution is available only in Hungarian. Google translation
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 sorozatából kiválasztható egy részsorozat úgy, hogy 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 részsorozatot úgy, hogy . Mivel feltevésünk értelmében a számok között csak véges sok olyan lehet, amelyik nem nagyobb kin-nél, léteznie kell olyan in+1>in indexnek, amelyre kin+1>kin, vagyis a részsorozat folytatható.
Legyenek most adva tengelypárhuzamos téglatestek, amelyek egyik csúcsa az origó, és minden csúcs koordinátái nemnegatív egész számok. A Ti téglatest egyértelműen megadható az origóval szemközti csúcsával, melynek koordinátái legyenek (xi,yi,zi). Itt xi,yi,zi tehát nemnegatív egész számok. Ti pontosan akkor tartalmazza Tj-t, ha xixj, yiyj és zizj egyszerre teljesül. A fenti észrevétel értelmében létezik egy olyan indexsorozat, melyre teljesül. Ebből az indexsorozatból kiválasztható egy olyan indexsorozat, amelyre is teljesül. Végül ebből kiválaszthatunk egy indexsorozatot, amelyre is fennáll. Ekkor pedig a téglák részsorozatára teljesülni fog bármely i<j esetén, hogy xcixcj, yciycj és zcizcj, vagyis a Tcj téglatest tartalmazza a Tci téglát.
Statistics:
56 students sent a solution. 5 points: 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 points: Wang Daqian. 3 points: 1 student. 2 points: 2 students. 1 point: 2 students. 0 point: 11 students.
Problems in Mathematics of KöMaL, May 2008