Gönderen Konu: Tübitak Lise 2. Aşama 2005 Soru 3  (Okunma sayısı 2326 defa)

Çevrimdışı geo

  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 1699
  • Karma: +8/-0
Tübitak Lise 2. Aşama 2005 Soru 3
« : Ağustos 06, 2013, 04:36:37 öö »
$n+1$ kentin bulunduğu bir ülkede, bu kentlerden bazıları arasında karşılıklı uçak seferleri yapılmaktadır. $A$ ve $B$ kentleri arasında yapılan bir karşılıklı sefer, aynı gün içinde hem $A $ dan $B$ ye, hem de $B$ den $A$ ya yapılan bir uçuş ikilisi anlamına gelip, bir kentten diğerine karşılıklı olmayan tek yönlü bir sefer mevut değildir. İki kent arasında aynı gün içinde birden çok sayıda karşılıklı sefer yapılabilmektedir. İki kent arasında aynı gün içinde birden çok sayıda karşılıklı sefer yapılabilmektedir. $A$ kenti için, bir günde $A$ dan kalkan uçak sayısını $d_{A}$ ile gösteriyoruz. Başkent dışındaki tüm $A$ kentleri için $d_{A}\le n$ ve yine başkent dışındaki ve aralarında karşılıklı uçak seferi bulunmayan farklı herhangi iki $A$, $B$ kenti için, $ d_{A}+d_{B}\le n$ koşulları sağlanmaktadır. $n+1$ kent arasında yer alan başkentten bir gün içinde yapılan uçak seferlerinin sayısı konusunda ise, herhangi bir kısıtlama yoktur.

Bu ülkede bir günde en çok kaç karşılıklı uçak seferi yapılabileceğini ve bu en çok karşılıklı sefer sayısını olanaklı kılan tüm uçuş çizelgelerini belirleyiniz.
« Son Düzenleme: Ağustos 27, 2013, 04:28:48 ös Gönderen: bosbeles »

Çevrimdışı geo

  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 1699
  • Karma: +8/-0
Ynt: 3
« Yanıtla #1 : Ağustos 17, 2013, 11:48:05 ös »
(Sinan KARAL)

İddiamız en fazla $\dbinom{n+1}{2}$ sefer olabileceğidir.

Kentlerimiz $V_1,V_2, \cdots V_n$ ve başkentimiz de $V$ olsun.
$V_i$ şehrinden başkente giden seferlerin sayısı $b_i$, $V_i$'nin başkent dışında seferi olduğu şehirlerin sayısı $r_i$ olsun.$V$ den çıkan yolların sayısı $y,$  $(V_1, \cdots , V_n)$ arasındaki yolların sayısı $x$ olsun.

Tüm $(V_i,V_j)_{(i\neq j)}$ ikilileri üzerinden seferleri sayalım.Bir $V_i$ ve $V_j$ ikilisi aldığımızda, bu ikisinden çıkan seferlerin toplam sayısı (bir seferi iki kez de sayabiliriz, farketmez.)

$d_{V_i}+d_{V_j}=b_i+b_j+(d_{V_i}-b_i)+(d_{V_j}-b_j)$ dir. Yani bu saymada $\displaystyle \sum_{i\neq j}(d_{V_i}+d_{V_j})$
toplamında $V$ den çıkan her sefer (mesela $V$ ile $V_1$ arasında bir yol) $d_{V_1}$ bu toplamda kaç kez geçmişse o kadar kez, yani $2n-2$ kez sayılır.Bir $V_i$ ve $V_j$ yi bağlayan sefer ise $d_{V_i}$ ve $d_{V_j}$ kaç kez geçmişse o kadar yani $2(2n-2)=4n-4$ kez sayılır.

Dolayısıyla $\displaystyle \sum_{i\neq j}(d_{V_i}+d_{V_j})=(2n-2)Y+(4n-4)X$ bulunur.... $(1)$

Diğer taraftan, $\displaystyle \sum_{i\neq j}(d_{V_i}+d_{V_j})=\displaystyle \sum_{i=1}^n  \displaystyle \sum_{i\neq j}(d_{V_j}+d_{V_i})$ sağlanır.Yani $V_i$ şehrini sabit tutarak toplamı inceleyelim :
$V_i$'den sefer olan şehirler $V_{k_1},V_{k_2},\cdots , V_{k_{r_i}}$ olsun. Dolayısıyla bir $j\neq k_{\ell}$ için $V_i+V_j \leq n$ yazabiliriz :
$\displaystyle \sum_{i=1}^n  \displaystyle \sum_{i\neq j}(d_{V_j}+d_{V_i})=\displaystyle \sum_{i=1}^n \left [\displaystyle \sum_{j\neq i,k_1,k_2, \cdots ,k_{r_i}}(d_{V_i}+d_{V_j})+\displaystyle \sum_{j\in k_1,k_2, \cdots ,k_{r_i}}(d_{V_i}+d_{V_j})\right]$

$\leq \displaystyle \sum_{i=1}^n \left [\displaystyle \sum_{j\neq i,k_1,k_2, \cdots ,k_{r_i}}n+\displaystyle \sum_{j\in k_1,k_2, \cdots ,k_{r_i}}(n+n)\right]$

$=\displaystyle \sum_{i=1}^n \left[n(n-r_i-1)+2n.r_i\right] = \displaystyle \sum_{i=1}^n (n^2-n+nr_i)=n^3-n^2+n(r_1+ \cdots +r_n)$

$r_1+ \cdots +r_n \leq 2X$ sağlanır, çünkü $r_1+ \cdots +r_n$ toplamı $V_1, \cdots ,V_n$ arasındaki toplam sefer sayısından küçük eşittir.($V_i$ şehrinden diğer şehirlere en az $r_i$ sefer vardır.)

$\implies$ $(1)$'i de kullanarak : $(2n-2)Y+(4n-4)X \leq n^3-n^2+2X.n$

$\implies$ $(2n-2)(x+y) \leq [2X-(n^2-n)]+[n^3-n]$

$\implies$ $x+y \leq \left[ \dfrac{2X-n^2+n}{2n-2} \right] + \dbinom{n+1}{2}$ bulunur.

$x+y \leq \dbinom{n+1}{2}$ olduğunu ispatlamak istiyoruz. $2X \leq n^2-n$ ise sorun yok. $2X > n^2-n$ olsun. Dolayısıyla her $V_a$ ile $V_b$ arasında en az 1 sefer olmalı, aksi takdirde $d_{V_A}+d_{V_b} \leq n$ olur ve $\displaystyle \sum_{i\neq a,b} d_{V_i} \leq n$ olduğundan : $2X \leq \displaystyle \sum_{i=1}^n d_{V_i} \leq n+(n-2)n = n^2-n$ olur, çelişki.

Yani her $V_a$ ve $V_b$ arasında sefer var. Bu durumda her $V_i$ şehrinden en az $n-1$ sefer başkent dışındaki şehirlere olacağından, $V_i$ şehrinin mümkün $n.$ seferi ya başkente ya da başka bir şehredir.Yani $Y\leq n$ olur ve tam $n-Y$ şehrin başkent dışındaki şehirlere en fazla $n$ seferi olur.

$\implies$ $2X \leq (n-Y)+(n^2-n)$, $x+y \leq \frac{n^2-n}{2}+ \frac{n+Y}{2} \leq \frac{n^2-n}{2}+n = \binom{n+1}{2}$

Demek ki bu durumda zaten $x+y \leq \binom{n+1}{2}$.
Sonuç olarak, $x+y \leq \dbinom{n+1}{2}$ bulunur ve eşitlik durumunun sağlanması için :

$i)$ $2X \leq n^2-n$ iken, $i=1, \cdots ,n$ için $r_i=d_{V_i}-b_i$ olacak, yani her $V_i$ şehrinden başka şehirlere en fazla 1 sefer olacak. Ayrıca $X= \dbinom{n}{2}$ olacak, yani başkent dışında her şehir arasında tam 1 sefer var. $Y=n$ olacağından, başkentten de diğer her şehre tam 1 sefer var. Yani ülkedeki her şehir arasında o gün içinde karşılıklı tam 1 sefer var, bu durumda şartların sağlandığı açıktır.

$ii)$ $2X > n^2-n$ iken, eşitlik durumu için $Y=n$ olmalı,

yani $X= \dbinom{n+1}{2}-Y= \dfrac{n^2-n}{2}$, çelişiki!

Demek ki bu durumda eşitlik olamaz.

İspat biter.
« Son Düzenleme: Haziran 22, 2014, 09:06:19 öö 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 
SimplePortal 2.3.3 © 2008-2010, SimplePortal