Gönderen Konu: Tübitak Lise 1. Aşama 2011 Soru 36  (Okunma sayısı 3387 defa)

Çevrimdışı ERhan ERdoğan

  • G.O Genel Moderator
  • Geo-Maniac
  • ********
  • İleti: 1421
  • Karma: +12/-0
Tübitak Lise 1. Aşama 2011 Soru 36
« : Eylül 04, 2013, 03: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}
$
« Son Düzenleme: Mayıs 12, 2014, 11:16:04 öö Gönderen: geo »

Çevrimdışı geo

  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 1812
  • Karma: +8/-0
Ynt: Tübitak Lise 1. Aşama 2011 Soru 36
« Yanıtla #1 : Ağustos 11, 2014, 10:26:25 ös »
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) 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.
« Son Düzenleme: Ağustos 12, 2014, 01:13:34 öö 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