Gönderen Konu: Tübitak Lise 2. Aşama 2011 Soru 6  (Okunma sayısı 3847 defa)

Çevrimdışı geo

  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 2492
  • Karma: +9/-0
Tübitak Lise 2. Aşama 2011 Soru 6
« : Ağustos 06, 2013, 04: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)
« Son Düzenleme: Kasım 13, 2013, 02:51:05 ös Gönderen: geo »

Çevrimdışı geo

  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 2492
  • Karma: +9/-0
Ynt: 6
« Yanıtla #1 : Ağustos 18, 2013, 01:08:22 öö »
(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.
« Son Düzenleme: Haziran 22, 2014, 09:09:17 öö 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 35 36 37 
SimplePortal 2.3.3 © 2008-2010, SimplePortal