Geomania.Org Forumları
Yarışma Soruları => Tübitak Lise 1. Aşama => 2011 => Konuyu başlatan: ERhan ERdoğan - Eylül 04, 2013, 02:04:35 öö
-
Boyları birbirinden farklı $14$ öğrenci başlangıçta nasıl sıralanmış olurlarsa olsunlar, her adımda yan yana duran iki öğrencinin yerini değiştirerek en az kaç adımda öğrencileri boy sırasına sokmak mümkün olur?
$
\textbf{a)}\ 42
\qquad\textbf{b)}\ 43
\qquad\textbf{c)}\ 45
\qquad\textbf{d)}\ 52
\qquad\textbf{e)}\ \text{Hiçbiri}
$
-
Yanıt: $\boxed{C}$
Boyları $1,2,\dots, 14$ kabul edelim.
$ p = \left(\begin{array}{cccccc}
1 & 2 & 3 & \cdots & 13 & 14 \\
p(1) & p(2) & p(3) & \cdots & p(13) & p(14)
\end{array} \right)$
$p$ permütasyonunda $i<j$ olmak üzere $p(i)>p(j)$ ise $(i,j)$ çiftine $p$ nin bir inversiyonu (bkz. inversion (http://en.wikipedia.org/wiki/Inversion_(discrete_mathematics))) diyoruz.
$p$ artan sırada olduğunda toplam inversiyon sayısı $0$ dır.
$p$ azalan sırada olduğunda toplam inversiyon sayısı $\dbinom {14}{2} = 91$ dir.
$p$ için $(i,j)$ çifti sayısı da $\dbinom {14}{2} = 91$ dir. Yani ters sıralı permütasyon en çok inversiyona sahip permütasyondur.
Bu soru için $p$ nin inversiyon sayısını çift yönlü düşünelim.
Örneğin, artan sıralı bir $p$ için artan inversiyon sayısı $0$, azalan inversiyon sayısı $91$ dir. Bu durumu $(0,91)$ ile gösterelim.
Azalan sıralı $p$ için inversiyon sayısı çifti $(91,0)$ olacaktır.
$(x,y)$ artan-azalan inversiyon sayısı çiftine sahip herhangi bir $p$ permütasyonunda komşu iki elemanı yer değiştirdiğimizde, $a=1,-1$ için, $(x,y) \to(x+a,y-a)$ olacaktır. Bu durumda $x+y$ toplamı değişmemiş olacak. O halde herhangi bir $p$ permütasyonu için inversiyon çifti toplamı $x+y = 0+91=91+0= 91$ dir.
Bu durumda olası tüm $(x,y)$ inversiyon sayısı çiftlerinden $\min\{x,y\}$ değeri en çok $45$ olabilir.
$ p = \left(\begin{array}{cccccccccccccc}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\
10 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 11 & 12 & 13 & 14
\end{array} \right)$ permütasyonunun inversiyon sayısı çifti $(45,46)$ dır.
Şimdi soruya dönelim:
Her yer değiştirmede inversiyon sayısı en fazla $1$ azalacağı için bir permütasyonu artan sıralamak için gerekli yer değiştirme sayısı en az toplam inversiyon sayısı kadar olmalı. Aslında tam olarak toplam inversiyon sayısı kadar yer değiştirme yeterlidir. Bunu ispatlayalım:
- İnversiyon oluşturan bir ardışık çifti yer değiştirdiğimizde, toplam inversiyon sayısı $1$ azalacaktır.
- Herhangi bir adımda ardışık çiftlerin hiçbiri bir inversiyon oluşturmuyorsa $p(1)<p(2)<\dots < p(n)$ demektir.
- O halde toplam inversiyon sayısı kadar ardışık yer değiştirmede toplam inversiyon sayısını sıfırlayabiliriz, yani permütasyonu artan sıralı hale dönüştürebiliriz.
Toparlamak gerekirse $ p = \left(\begin{array}{cccccccccccccc}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\
10 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 11 & 12 & 13 & 14
\end{array} \right)$ permütasyonunda artan inversiyon sayısı $45$, azalan inversiyon sayısı $46$ olduğu için $p$ permütasyonunu $45$ ardışık yer değiştirme ile artan hale getirebiliriz.