Tübitak Ortaokul 1.Aşama 2015 Soru 08

[ERhan ERdoğan]

$1,2, \cdots , 20$ sayıları ile numaralandırılmış $20$ top başlangıçta rastgele dizilmiştir. Her işlemde aralarında en az $\ell$ adet top bulunan iki topun yerlerini değiştirerek bir kaç işlem sonucunda topları numaralarına göre artan sırada dizebiliyorsak, $\ell$ nin alabileceği en büyük değer nedir ? 

$
\textbf{a)}\ 7
\qquad\textbf{b)}\ 8
\qquad\textbf{c)}\ 9
\qquad\textbf{d)}\ 10
\qquad\textbf{e)}\ 11
$

[borlu51]

Bu sorunun çözümünde yardımcı olabilecek var mı?

[kriptoman]

Sayıları iki gruba bölün ilk 10 ve son 10. ilk grubun sonuncusu ile ikinci grubun 1.si nin atlatabileceğiniz yerlere bakın burdan l 10 dan küçük geliyo olması lazım (bu sadece bir ipucu çözüm değil)

[borlu51]

yine de teşekkürler kardeşim.

[Lokman Gökçe]

Yanıt: $\boxed{C}$

Eğer $\ell \geq 10$ olursa $10.$ sıradaki ve $11.$ sıradaki sayılar yerlerinden kımıldatılamaz. Dolayısıyla bu sayıların yerinde farklı sayıların olduğu bir senaryoda toplar artan sırada dizilemez. $\ell \leq 9$ olmalı. Şimdi de $\ell_{\max} = 9$ olduğunu ispatlayalım.


Öncelikle $1.$ sıraya ve $20.$ sıraya dikkat edelim. Bu sıralara "park yeri" ismi verelim. $1-10$ aralığındaki yerlere sıralanmış ardışık iki topun yerini, $20.$ sıradaki park yerini kullanarak değiştirebiliyoruz. Şöyle:  $1-10$ aralığındaki ardışık konumda bulunan iki topun numaraları $a$ ve $b$ olsun. $20$. sıradaki park yerinde de $c$ numaralı top olduğunu düşünelim. Yani $--ab----c$ dizilimi olsun.

1. hamlede $a$ ile $c$ nin yeri değişir. $--cb----a$ olur.
2. hamlede $a$ ile $b$ nin yeri değişir. $--ca----b$ olur.
3. hamlede $c$ ile $b$ nin yeri değişir. $--ba----c$ olur.

3 hamlenin sonunda yalnızca $a$ ve $b$ numaralı topların konumlarını değiştirdik. Diğer topların yeri değişmedi. Benzer şekilde,  $11-20$ aralığındaki yerlere sıralanmış ardışık iki topun yerini, $1.$ sıradaki park yerini kullanarak değiştirebiliriz. Özel olarak $10.$ ve $11.$ sıradaki topların yerleri de $5$ hamlede değiştirilebiliyor. Her iki uçtaki park yerini de kullanarak bunu örneklemek kolaydır. Böylece, ardışık olarak verilen herhangi iki topun yerini değiştirebildiğimizi anlıyoruz.

Bir dizide yan yana yanlış sıralanmış iki elemanı doğru sıraya getirme işlemimiz (komşuların değişimi) varsa, bu işlemi tekrar edersek en sonunda tüm dizi küçükten büyüğe sıralayabiliriz. Bu bize, topların sıralaması nasıl verilirse verilsin $\ell = 9$ iken artan sıralama yapmanın mümkün olduğunu gösterir.