Geomania.Org Forumları
Yarışma Soruları => Tübitak Lise 2. Aşama => 2011 => Konuyu başlatan: geo - Ağustos 06, 2013, 03:47:49 öö
-
$A$ ülkesindeki $2011$ kent ile $B$ ülkesindeki $2011$ kent arasında karşılıklı uçak seferleri yapılıyor. İki kent arasındaki seferleri yalnızca bir hava yolu şirketi işletebiliyor ve bir kentten çıkan seferleri en çok $19$ farklı hava yolu şirketi işletebiliyor. Uçuşlar hava yolu şirketleri arasında bu koşulları sağlayacak biçimde nasıl paylaşılmış olursa olsun, yalnızca bir tek hava yolu şirketinin uçuşlarını kullanarak herhangi ikisi arasında gidebileceğimiz $k$ kent bulunuyorsa, $k$ nin alabileceği en büyük değeri belirleyiniz.
(Azer Kerimov)
-
(Yunus Emre DEMİRCİ)
Önce $212$ için örnek verelim.
$A$ daki ve $B$ deki kentleri, her iki ülkede de $16$ tane $106$ kent ve $3$ tane $105$ kent olmak üzere $19$'ar gruba ayıralım. Bu gruplar arasındaki uçuşları farklı havayolu şirketleri kontrol etsin (Uçuşlar bir ülkeden diğerine olduğu için toplam $19^2$ havayolu şirketi olması gerekir). Bu durumda aynı havayolu şirketi kullanılarak en çok $212$ kente ulaşılabilir.
Şimdi uygun havayolu ile her zaman $212$ kente ulaşmanın mümkün olduğunu gösterelim.
$i \in \{1, 2, \ldots s\}$ olmak üzere, havayolu şirketi değiştirmeden ulaşılabilen kentlerin kümesi $K_i$, kentlerin sayısı ise $k_i$ olsun (bir havayolu şirketi için birden fazla küme bulunabilir). Soruda verilen şarttan dolayı her kent en fazla $19$ kümenin içinde olabilir. Yani, toplamda $4022$ kent olduğundan, $\sum_{i=1}^{n} k_i \leq 4022 \cdot 19$ dur.
Öte yandan, $i$ havayolu şirketi, $K_i$ 'de bulunan kentler arasında en fazla $\frac{k_i^2}{4}$ uçuş düzenleyebilir. Toplam uçuş sayısı $2011^2$ olduğundan $\sum_{i=1}^{n} \frac{k_i^2}{4} \geq 2011^2$, yani $\sum_{i=1}^{n} k_i^2 \geq 4 \cdot 2011^2$ olur.
Şimdi, $k_i$ 'lerden en az biri $212$'den büyükse ispat biter.
Hepsinin en çok $211$ olduğu duruma bakalım. Yani, $\sum_{i=1}^{n} k_i \leq 4022 \cdot 19$ ve $k_i \leq 211$ iken, $\sum_{i=1}^{n} k_i^2$ nin alabileceği en büyük değere bakalım. $a\geq b>0$ iken, $(a+1)^2+(b-1)^2>a^2+b^2$ olduğundan, $\sum_{i=1}^{n} k_i^2$ en büyük değerini $k_i$ lerin hemen hemen hepsi $211$ iken alır. $363\cdot 211 > 4002 \cdot 38$ olduğundan $363\cdot 211^2 \geq \sum_{i=1}^{n} k_i^2 \geq 4\cdot 2011^2$ olur. Fakat $363\cdot 211^2 < 4\cdot 2011^2$ olduğundan, bu durum mümkün değildir.