Geomania'da ki değişiklikleri sosyal medyada takip etmek için Anasayfamızda ki "Beğen" butonuna tıklayınız.
Ana Sayfa
Forum
Yardım
Blog
Giriş Yap
Kayıt Ol
Geomania.Org Forumları »
Yarışma Soruları »
Tübitak Lise 2. Aşama »
2015 »
Tübitak Lise 2. Aşama 2015 Soru 4
« önceki sonraki »
Yazdır
Sayfa: [1] Aşağı git
Gönderen Konu: Tübitak Lise 2. Aşama 2015 Soru 4 (Okunma sayısı 2421 defa)
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 »
Tweet
$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 »
Kayıtlı
Matematik bilimlerin sultanıdır
-Carl Friedrich Gauss
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 »
Tweet
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.