Uluslararası Matematik Olimpiyatı 2017 Soru 5

[Eray]

$N\ge2$ verilmiş bir tam sayı olsun. Herhangi ikisinin boyları birbirinden farklı olan $N(N+1)$ futbolcu bir şekilde yan yana sıraya dizilmiştir. Takımın antrenörü bu sıradan $N(N-1)$ futbolcuyu öyle çıkarmak istiyor ki geriye kalan $2N$ futbolcudan oluşan yeni sıra aşağıdaki $N$ adet şartı sağlasın:

$\quad  (1)$ En uzun futbolcu ile ikinci en uzun futbolcu arasında kimse olmayacak,

$\quad  (2)$ Üçüncü en uzun futbolcu ile dördüncü en uzun futbolcu arasında kimse olmayacak,

$\quad \;\;\vdots$

$\quad (N)$ İkinci en kısa futbolcu ile en kısa futbolcu arasında kimse olmayacak.

Antrenörün bunu her zaman yapabileceğini gösteriniz.

[nk6]

Oyuncuların boy sıralamalarını düşünelim, kısadan uzuna her biri $N+1$ kişi içeren $N$ gruba ayıralım. Şimdi solda sağa dizilişteki ilk kişilere bakalım, aynı gruptan iki kişi bulduğumuz anda duralım, bu iki kişiyi seçelim, geldiğimiz yere kadar olan kişileri, bu iki kişinin bulunduğu gruptaki kalan kişileri atalım. Gözlemleyelim ki bazı boy gruplarından $1$ kişi attık, bazılarından hiç atmadık. Hiç atmadıklarımızdan da rastgele seçtiğimiz bir kişiyi atalım.

Tam olarak $2N$ kişi atmış oluruz, ayrıca başta oluşturduğumuz $N$ boy grubundan $N-1$ tanesi $N$ kişiyle hala durmaktadır, dolayısıyla tümevarımsal olarak aynı işlemi tekrarlarsak her boy grubundan bir ikiliyi sırada birbiriyle kesişmeyecek şekilde seçmiş oluruz, ispat biter.