Tübitak Lise 1. Aşama 2015 Soru 32

[ERhan ERdoğan]

$23$ kentin bulunduğu bir ülkede $250$ kent ikilisi arasında karşılıklı uçak seferleri, ülkedeki herhangi bir kentten bir diğerine (doğrudan veya birkaç aktarmayla) en fazla $5$ saatlik uçus süresi sonucunda ulaşılabilecek biçimde nasıl düzenlenirse düzenlensin, $k$ saatlik uçus sonucunda bir kentten başlayıp her kente en az bir kez uğrayarak baştaki kente dönülebiliyorsa, $k$ nın alabileceği en küçük değer nedir?

$
\textbf{a)}\ 95
\qquad\textbf{b)}\ 100
\qquad\textbf{c)}\ 105
\qquad\textbf{d)}\ 110
\qquad\textbf{e)}\ 115
$

[Alimmm78]

Toplam yol sayısı (23,2) = 253
Elimizde 250 yol var yani 3 yolumuz eksik
Şehirler a1 ,a2 , ...,a23 olsun
 Bu eksik üç yol şu şekilde olabilir

a1-a2 , a5-a6, a20-a21 ( ardışık ikililerden herhangi üçünü yazdım) ( a1-a2,a2-a3,a3-a4 te bunun gibi )
Veya
a1-a2, a1-a3, a2-a3 ( herhangi ardışık üçlünün birinin arasında olan yollar (3,2) lisi 3 plduğu için 3 yol var.
Bu iki seçeneğe bakacağız
İlk seçeneğe bakınca a1den a2 ye 5 saatte gidiyormuş. O zaman herhangi bir ak üzerinden giderken a1-ak-a2 beş saat
A5-am-a6 yı de 5 saatte gidecek ( düzenleyici kişi k m lerı farklı yaparsa daha birinden birine giderken daha fazla şehiri gezdiğimiz için yol kısalacaktıe o yüzden k=m olu )
Bu üç ikiliden aynı ak  üzerinden gitmemiz laZım
Bu şekilde olunca k yı 9 alalım.
A1-a9-a2-a3-a4-a5-a9-a6-a7-a8-a10-a11-a12-a13-a14-a15-a16-a17-a18-a19-a20-a9-a21-a22-a23-a1
22.5 ten cevap 110 oluyor
Başta dediğim ikinci seçenek te bununla aynı şekilde 110 çıkıyor

[geo]

Yanıt: $\boxed D$

Cevap: $110$.
$250 < \dbinom{23}{2} = 253$ olduğundan aralarında karşılıklı uçak seferleri bulunmayan en az iki kent vardır. Buna göre $A$ dan $B$ ye en kısa sefer $A \rightarrow  C\rightarrow B$ olacak şekilde $A$, $B$ ve $C$ kentleri bulunur. O zaman $A \rightarrow C \rightarrow B \rightarrow \cdots \rightarrow A$ en fazla $22 \cdot 5 = 110$ saat olur. $110$ saat için örnek: Bir $A$ kenti ile diğer tüm kentler arasında her biri $2.5$ saat süren karşılıklı uçak seferleri olsun. $A$ dışındaki kenlerin bazıları arasında da toplam $100$ sefer elde etmek için her biri $10$ saat süren yollarla birleştirilsin.

Kaynak: Tübitak 23. Ulusal Matematik Olimpiyatı Birinci Aşama Sınav Soru ve Çözümleri 2015