Geomania.Org Forumları
Fantezi Cebir => Kombinatorik => Konuyu başlatan: sarmaticus - Haziran 05, 2021, 12:18:37 ös
-
$a_1,a_2,a_3,\dots, a_{26}$ farklı reel sayıları veriliyor. Dizideki yerlerini değiştirmeksizin bu sayılar arasında artan veya azalan sırada en fazla kaç terim seçmeyi garantileriz?
a)3 b)4 c)5 d)6 e)7
-
$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(26)$ sıralı ikilileri birbirinden farklıdır. $1\leq x_i\leq 5$ ve $1 \leq y_i \leq 5$ olduğunda en fazla $25$ sıralı ikili tanımlanabileceği için en az bir $i$ değeri için $x_i > 5$ veya $y_i>5$ olmalı. Yani herhangi bir $a_i$ dizisi için $f(26)=\max(x_{26}, y_{26}) > 5$ olmalı.
$1,2,3,\dots,26$ dizisini düşünelim. $x_i = 26$ olabiliyor.
$26,25, \dots, 1$ dizisini düşünelim. $y_i = 26$ olabiliyor.
$5,4,3,2,1,10,9,8,7,6,15,14,13,12,11,20,19,18,17,16,25,24,23,22,21,26$ dizisini düşünelim. $x_i = 6$ olabiliyor, daha fazla olamıyor.
O halde doğru yanıt $\text {d} )\ 6$.
Daha ayrıntılı bilgi için Erdös-Szekeres Theorem (https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem).