Tübitak Lise 1. Aşama 1996 Soru 29

[matematikolimpiyati]

Farklı boylarda $17$  kişi yan yana dizilmiş olsun. Bunlardan $n$  tanesi artan ya da azalan bir boy sırasında kalacak şekilde geri kalanlar sıradan uzaklaştırılıyor. Bu diziliş ne olursa olsun, böyle bir işlemi olanaklı kılan en büyük $n$  sayısı aşağıdakilerden hangisidir?

$\textbf{a)}\ 8  \qquad\textbf{b)}\ 7  \qquad\textbf{c)}\ 6  \qquad\textbf{d)}\ 5  \qquad\textbf{e)}\ 4$

[geo]

Yanıt: $\boxed D$

$i.$ kişinin boyu $a_i$ olsun.
$x_i$ ile $a_i$ ye kadar olan en büyük artan alt dizinin eleman sayısını, $y_i$ ile de $a_i$ ye kadar olan en büyük azalan alt dizinin eleman sayısını gösterelim.
$f(i)=(x_i, y_i)$ sıralı ikilileri için $i\neq j$ iken $f(i) \neq f(j)$ dir. (Çünkü dizide $a_i$ den sonra gelen sayı $a_i$ den büyük olduğunda $x_{i+1} = x_i + 1$, küçük olduğunda $y_{i+1} = y_i + 1$ olacaktır.)
Bu durumda $f(1), f(2), \dots, f(17)$ sıralı ikilileri birbirinden farklıdır. $1\leq x_i\leq 4$ ve $1 \leq y_i \leq 4$ olduğunda en fazla $16$ sıralı ikili tanımlanabileceği için en az bir $i$ değeri için $x_i > 4$ veya $y_i>4$ olmalı. Yani herhangi bir $\{ a_i \}$ dizisi için $\max(f(17))=\max(x_{17}, y_{17}) > 4$ olmalı.

$1,2,3,\dots,17$ dizisini düşünelim. $x_{17}= 17 $ olabiliyor.
$17,16, \dots, 1$ dizisini düşünelim. $y_{17}= 17$ olabiliyor.
$4,3,2,1,8,7,6,5,12,11,10,9,16,15,14,13,17$ dizisini düşünelim. $x_{17} = 5$ olabiliyor, daha fazla olamıyor.

O halde doğru yanıt $\text {d} )\ 5$.

Daha ayrıntılı bilgi için Erdös-Szekeres Theorem.