Geomania.Org Forumları
Yarışma Soruları => Tübitak Lise 1. Aşama => 1996 => Konuyu başlatan: matematikolimpiyati - Şubat 03, 2023, 03:59:32 ös
-
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$
-
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 (https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem).