Gönderen Konu: Artan ya da azalan en büyük alt dizi  (Okunma sayısı 107 defa)

Çevrimdışı sarmaticus

  • G.O Yeni Üye
  • *
  • İleti: 1
  • Karma: +0/-0
Artan ya da azalan en büyük alt dizi
« : 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

« Son Düzenleme: Haziran 05, 2021, 03:45:23 ös Gönderen: geo »

Çevrimdışı geo

  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 1784
  • Karma: +8/-0
Ynt: Artan ya da azalan en büyük alt dizi
« Yanıtla #1 : Haziran 06, 2021, 09:59:21 öö »
$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.


« Son Düzenleme: Haziran 06, 2021, 10:03:49 öö Gönderen: geo »

 


Sitemap 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 
SimplePortal 2.3.3 © 2008-2010, SimplePortal