Feladat:	2017. évi Nemzetközi Matematika Diákolimpia 22. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Borbényi Márton
Füzet:	2017/november, 451 - 452. oldal		PDF  |  MathML
Témakör(ök):	Nemzetközi Matematikai Diákolimpia, Kombinatorika
Hivatkozás(ok):	Feladatok: 2017/szeptember: 2017. évi Nemzetközi Matematika Diákolimpia 22. feladata

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   Borbényi Márton megoldása. Készítsünk $N$ csoportot az alábbi módon: az első csoportban legyen a sor szerint első $N+1$ ember, a másodikban a második $N+1$ ember, és így tovább. Célunk, hogy minden csoportból pontosan $2$ játékost válasszunk ki, így ők a megmaradó $2N$ embernél egymás mellé kerülnek. A következő algoritmust alkalmazzuk: ‐ elkezdjük jelölgetni a játékosokat magasság szerint csökkenő sorrendben; ‐ amint egy csoportban van két kijelölt focista, megállunk; ‐ elhagyjuk ebből a csoportból a két kijelölt játékoson kívül az összes embert, és minden más csoportból a csoport legmagasabb emberét; ‐ a két megjelölt játékossal már nem kell foglalkoznunk, hiszen a megmaradtak között ők ketten a legmagasabbak, és senki nem áll már közöttük; marad $N-1$ csoportunk, mindegyikben $N$ focistával; ‐ ismételjük a fenti eljárást az eggyel kisebb létszámú, eggyel kevesebb csoportból álló sorra stb.