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

Çevrimdışı geo

  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 1801
  • Karma: +8/-0
Tübitak Lise 2. Aşama 2009 Soru 3
« : Ağustos 06, 2013, 04:43:19 öö »
Bir beldenin Elektrik İşleri görevlisi Ahmet, $k$ gün boyunca her gün, ya seçtiği bir direkle yine kendisinin seçtiği istediği sayıda direk arasına birer tel bağlıyor, ya da en çok $17$ direk ikilisi seçip her ikiliye ait direkler arasına birer tel bağlıyor. Beldenin Boya İşleri görevlisi Berna da, beldede kaç direk olursa olsun ve Ahmet telleri nasıl bağlarsa bağlasın, beldedeki tüm direklerin en çok $2009 $ renk kullanarak ve aralarına tel bağlanmış herhangi iki direk aynı renkte olmayacak biçimde boyanabileceğini iddia ediyor. $k$ nin, Berna'nın iddiasının doğru olmasını sağlayan en büyük değerinin belirleyiniz.

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

Çevrimdışı geo

  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 1801
  • Karma: +8/-0
Ynt: 3
« Yanıtla #1 : Ağustos 24, 2013, 01:18:59 ös »
Cevap: $k$ nin en büyük değeri 2000 dir.

Ahmet' in seçtiği bir direkle yine kendisinin seçtiği istediği sayıda direk arasına birer tel bağlaması işlemine birinci işlem, en çok $17$ direk ikilisi seçip her ikiliye ait direkler arasına birer tel bağlaması işlemine de ikinci işlem diyelim.
Öncelikle $k\le 2000$ olduğunu ispatlayalım. $k>2001$  durumunda Ahmet $17$ direk seçip $\dfrac{\left(\genfrac{}{}{0pt}{}{17}{2}\right)}{17}=8$  bunların her ikilisi arasına tel bağlayıp, kalan direklerden $1993$ tanesini seçip $1993$ gün boyunca bunların her biriyle başlangıçta seçtiği $17$ direk ve bu $1993$ direkten işlem yaptığı dışındakiler arasına tel bağlanırsa $2001$ günün sonunda her ikilisi arasında tel bulunan, yani her ikilisinin farklı renkte boyanması gereken $1993+17=2010$ direk elde edilir. Ancak bu durumda Berna $2009$ renk ile istediği şekilde boyama yapamaz. O halde $k\le 2000$ dir.

Ahmet $2000$ günde ne yaparsa yapsın, Berna'nın iddiasını doğrulayabileceğini ispatlayalım. Ahmet birinci işlemi en fazla $2000$ kez yapacağından işlemi yapmak için seçtiği direk ile arasına tel bağladığı ancak işlem yapmadığı direkler en fazla $2000$ direğe bağlı olup, Ahmet'in işlem yapmak için seçtiği direkler $2009$ renk ile boyanabilirse, bu direkler bağlı oldukları direklerde kullanılmayan bir renkle boyanabileceği için bunları yok varsayabiliriz. Ahmet $a$ gün birinci işlemi, $b$ gün ikinci işlemi yapmış olsun. $a+b=2000$ dir. İlk işlemi yaptığı direkler kümesine $A$, ikinci işlemi yaptığı direkler kümesine $B$ diyelim. $|A|=a$  olup $A$  kümesi $a$ renk ile boyanır. $A$ daki tüm direklerle $B$ deki tüm direkler arasında tel bulunduğundan $B$ deki direklerin kendi aralarında $2009-a$  renk ile boyanabileceğini ispatlarsak Berna'nın iddiası doğru olur.

İddia: Aralarındaki tel sayısı $n\in {\mathbb N}$  için $\left(\genfrac{}{}{0pt}{}{n}{2}\right)$ ni aşmayan direkler en çok $n$ renk ile boyanabilir.

İspat: Aralarında hiç tel olmayan en çok direk içeren grubu alalım, daha sonra geriye kalanlara aynısını uygulayarak telleri gruplayalım. Grupları oluşturma şeklimizden dolayı herhangi iki farklı gruptan aralarında tel bulunan birer direk bulunur. O halde grup sayısına $m$ dersek en az $\left(\genfrac{}{}{0pt}{}{m}{2}\right)$ tel bulunur. $\left(\genfrac{}{}{0pt}{}{m}{2}\right)\le \left(\genfrac{}{}{0pt}{}{n}{2}\right)$ olup $m\le n$ dir. Her grubu bir renge boyarsak direkler an fazla $n$ renk ile boyanmış olur ve iddiayı ispatlamış oluruz.

$b{\in {\mathbb N}}_0$ olup $(b-8)(b-9)\ge 0\Rightarrow b^2-17b+72\ge 0\Rightarrow b^2+17b+72\ge 34b\Rightarrow (b+9)(b+8)\ge 34b\Rightarrow \left(\genfrac{}{}{0pt}{}{b+9}{2}\right)\ge 17b$ olup iddiadan  $B$ deki direkler en çok $b+9$ renk ile boyanabiliyor. O halde tüm direkler en çok $a+(b+9)=2000+9=2009$ renk ile boyanabiliyor. Sonuç olarak cevap $k=2000$ dir.
« Son Düzenleme: Haziran 22, 2014, 09:07:44 öö 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 
SimplePortal 2.3.3 © 2008-2010, SimplePortal