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

Çevrimdışı geo

  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 2492
  • Karma: +9/-0
Tübitak Lise 2. Aşama 2006 Soru 2
« : Ağustos 06, 2013, 04:38:05 öö »
$2006$ öğrenci ve $14$ öğretmenin bulunduğu bir okulda, her öğrencinin en az bir öğretmen ile tanışık olması koşuluyla, öğretmenler ve öğrenciler arasındaki tanışıklı bağıntısı ne olursa olsun; öğretmenin tanıdığı öğrenci sayısının, öğrencinin tanıdığı öğretmen sayısına oranının en az $t$ olduğu, birbirini tanıyan bir öğrenci-öğretmen ikilisinin bulunmasını sağlayan en büyük $t$ gerçel sayısını belirleyiniz.

(Azer Kerimov)
« Son Düzenleme: Kasım 13, 2013, 02:44:28 ös Gönderen: geo »

Çevrimdışı geo

  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 2492
  • Karma: +9/-0
Ynt: 2 - Tashih edildi
« Yanıtla #1 : Ağustos 24, 2013, 11:48:40 öö »
Cevap: $t=\dfrac{2006}{14}$. 

Tüm öğrencilerin öğretmenlerle tanışık olduğu durumu düşünürsek tüm öğrenci ve öğretmen ikilileri için bu oran $\frac{2006}{14}$ e eşittir ve dolayısıyla $t\leq \frac{2006}{14}$  elde ederiz.

Şimdi $t=\frac{2006}{14}$  ün istenen şartı sağlayacağını ispatlamamız yeterlidir. $1\leq i \leq 14$  için, $a_i$ ile, $i.$ öğretmenin tanıdığı öğrenci sayısını; $1\leq j \leq 2006$  için, $b_j$ ile de $j.$ öğrencinin tanıdığı öğretmen sayısını gösterelim. Öğrencilerimizi $1$ den $2006$ ya kadar, öğretmenlerimizi de $1$ den $14$ e kadar numaralandıralım.  $T$, birbirini tanıyan tüm $(i,j)$ öğretmen-öğrenci ikililerinin kümesi olsun. Bu gösterimle, $\left |\{\ j:\ (i,j)\in T\ \}\right |=a_i \geq 0$ ve $\left |\{\ i:\ (i,j)\in T\ \} \right |=b_j \leq 1$ olduğunu gözlemleyelim.

$\dfrac{a_i}{b_j}$ oranının maksimum olmasını sağlayan $(i,j)\in T$ ikilisi vardır, bu ikili $(i_0,j_0)\in T$  olsun. Dolayısıyla $(i,j)\in T$  için, $\dfrac{{a_i}_0}{{b_j}_0} \geq \dfrac{a_i}{b_j}$  koşulunu sağlanır. Şimdi, tüm $(i,j)\in T$  için, $\dfrac{{a_i}_0}{b_{j_0}}\cdot \dfrac{1}{a_i} \geq \dfrac{1}{b_j}$  eşitsizliklerini toplarsak, $$\dfrac{{a_i}_0}{{b_j}_0}\cdot (\sum\limits_{(i,j)\in T}{\dfrac{1}{a_i}}) \geq \sum\limits_{(i,j)\in T}{\dfrac{1}{b_j}}$$ eşitsizliğini elde ederiz. Şimdi, $$\sum\limits_{(i,j)\in T}{\dfrac{1}{a_i}=\sum\limits^{14}_{i=1}{\sum\limits_{\{j:\ (i,j)\in T\}}{\dfrac{1}{a_i}}}}=\sum\limits^{14}_{i=1}{\dfrac{|\ \{j:\ (i,j)\in T\}\ |}{a_i}}=\sum\limits_{\{i:\ a_i \neq 0\}}{\dfrac{a_i}{a_i}}=\sum\limits_{\{i:a_i \neq 0\}}{1\leq 14}$$ ve benzer şekilde $$\sum\limits_{(i,j)\in T}{\dfrac{1}{b_j}=\sum\limits^{2006}_{j=1}{\sum\limits_{\{i:\ (i,j)\in T\}}{\dfrac{1}{b_j}}}}=\sum\limits^{2006}_{j=1}{\dfrac{|\ \{i:\ (i,j)\in T\}\ |}{b_j}}=\sum\limits^{2006}_{j=1}{\dfrac{b_j}{b_j}=\sum\limits^{2006}_{j=1}{1}}=2006$$ bulunur. Son eşitlikte eşitlik durumu vardır, çünkü sorudaki varsayım gereği her öğrenci en az bir öğretmen tanımaktadır.

Dolayısıyla $\dfrac{{a_i}_0}{{b_j}_0}\cdot 14 \geq \dfrac{{a_i}_0}{{b_j}_0}\cdot \sum\limits_{\left(i,j\right)\in T}{\dfrac{1}{a_i}} \leq \sum\limits_{\left(i,j\right)\in T}{\dfrac{1}{b_j}} \geq 2006\Rightarrow \ \dfrac{{a_i}_0}{{b_j}_0} \geq \dfrac{2006}{14}$ bulunur. Demek ki $(i_0,j_0)$ öğretmen-öğrenci ikilisi için bu oran $\geq \dfrac{2006}{14}$ dür, ispat biter.
« Son Düzenleme: Ekim 01, 2013, 11:36:01 öö 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