Gönderen Konu: Tübitak Lise 2. Aşama 2015 Soru 4  (Okunma sayısı 2421 defa)

Çevrimdışı Eray

  • G.O Genel Moderator
  • G.O Efsane Üye
  • ********
  • İleti: 381
  • Karma: +8/-0
Tübitak Lise 2. Aşama 2015 Soru 4
« : Aralık 06, 2015, 05:40:48 ös »
$2015$ tablonun gösterildiği bir sergide her katılımcı bir tablo ikilisi seçip tahtaya yazıyor. Sonra Sahte Sanatçı (S.S.) tahtada yazılı ikililerden bazılarını seçip, bu ikililerin her birinde tablolardan herhangi birini daha güzel olarak işaretliyor. Daha sonra sanatçının yardımcısı (S.Y.) her adımında tahtadaki henüz kıyaslanmamış bir $(A,C)$ tablo ikilisini, bir $B$ tablosu için tahtada $A$, $B$ den daha güzel ve $B$, $C$ den daha güzel olarak belirtilmişse, $A$, $C$ den daha güzel olarak işaretliyor. S.S., tahtaya hangi ikililer yazılmış olursa olsun en fazla $k$ ikiliyi kıyaslayarak S.Y. nin sonlu adım sonucunda tahtadaki tüm ikilileri kıyaslanmasını sağlayabiliyorsa, $k$ nın alabileceği en küçük değer nedir?

Not: S.Y, henüz kıyaslanmamış bir $(A_1, A_n)$ tablo ikilisini, $A_2, A_3\cdots , A_{n-1}$ tabloları için $A_1$, $A_2$ den daha güzel; $A_2$, $A_3$ ten daha güzel; ... ; $A_{n-1}$, $A_n$ den daha güzel olarak belirtilmişse, $A_1$, $A_n$ den daha güzel olarak işaretleyebiliyor.

(Azer Kerimov)
« Son Düzenleme: Şubat 28, 2016, 06:05:44 ös Gönderen: Eray »
Matematik bilimlerin sultanıdır
-Carl Friedrich Gauss

Çevrimdışı nk6

  • G.O İlgili Üye
  • **
  • İleti: 15
  • Karma: +0/-0
Ynt: Tübitak Lise 2. Aşama 2015 Soru 4
« Yanıtla #1 : Ağustos 09, 2017, 10:16:45 ös »
Cevap $2014$ (genel durum için $n-1$). Cevabın daha az olamayacağına örnek olarak $(1,i)$ ikililerinin yazılı olduğu duruma bakabiliriz.

Çözüm için $n$ tabloyu köşe olarak alan bir graf çizelim, Bir $1$ köşesi alıp kenarlarından birini kırmızıya boyayalım, ulaştığımız köşeye $2$ diyelim. Şimdi $2$ den daha önce ulaşmadığımız bir köşeye giden bir kenar seçelim, bu kenarı kırmızıya boyayıp ulaştığımız kenara $3$ diyelim. Eğer bir $i$ köşesine vardığımızda komşularının hepsi daha önce ulaşılmış köşeler ise $i-1$ köşesinin komşularına bakalım, orada da yeni köşe yoksa yine bir önceki numaralı köşeye bakalım, yeni köşe bulana kadar böyle devam edelim.

$n$ köşenin hepsine ulaştığımızda eğer grafımız bağlantılı ise $n-1$ kenar boyamış olacağız (eğer graf bağlantılı değilse orman oluşur, her ormanda köşe sayısının bir eksiği kadar kenar boyanır, dolayısıyla $n-1$ den az olur.) Boyalı $(i,j)$ kenarını $i$ den $j$ ye yönlendirelim, bu $i>j$ demek olsun. Bundan sonra boyalı olmayan kenarların da yönünün belirli olduğunu görelim.

Bir $(k,l), k<l$ kenarı için kenar boyamamızda $k$ ye $l$ den önce ulaşılmıştır, dolayısıyla bu kenar var olduğundan grafta da $k,k+1,\ldots ,l-1$ den herhangi biri $l$ ye kırmızı kenarla bağlıdır. Bu da $k>l$ olduğunun belirli olması için yeterlidir, ispat biter.
« Son Düzenleme: Ağustos 09, 2017, 10:20:07 ös Gönderen: nk6 »

 


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