Gönderen Konu: Tübitak Lise 1. Aşama 2015 Soru 24  (Okunma sayısı 4609 defa)

Çevrimdışı ERhan ERdoğan

  • G.O Genel Moderator
  • Geo-Maniac
  • ********
  • İleti: 1.424
  • Karma: +12/-0
Tübitak Lise 1. Aşama 2015 Soru 24
« : Haziran 18, 2015, 04:47:02 ös »
Bir sınıftaki $23$ öğrenci üç gruba, birbirleriyle arkadaş olan öğrenciler aynı grupta olmayacak şekilde tek türlü dağıtılabiliyorsa, sınıftaki arkadaş ikilisi sayısı en az kaç olabilir?

$
\textbf{a)}\ 41
\qquad\textbf{b)}\ 43
\qquad\textbf{c)}\ 46
\qquad\textbf{d)}\ 48
\qquad\textbf{e)}\ 50
$
« Son Düzenleme: Haziran 21, 2015, 10:06:48 öö Gönderen: geo »

Çevrimdışı çılgın

  • G.O İlgili Üye
  • **
  • İleti: 14
  • Karma: +1/-1
Ynt: Tübitak Lise 1. Aşama 2015 Soru 24
« Yanıtla #1 : Temmuz 02, 2015, 07:01:01 ös »
Yanıt: $\boxed{B}$

Öğrencilerden ilkini gruplardan birine yerleştiririz. İkinci öğrenciyi tek türlü yerleştirebilmemiz için ilk gruptaki öğrenci ile arkadaşlık bağı bulunmalıdır (bir bağ elde ettik), bu durumda bu öğrenciyi ikinci gruba yerleştiririz. Geri kalan $21$ öğrencinin her birinin tek türlü yerleşebilmesi için yerleşeceği grup haricindeki iki grupla da bir arkadaşlık bağı bulunması gereklidir ($21\cdot2=42$ bağ daha elde ettik). Yani tüm öğrencilerin tek türlü yerleşebileceği ve $43$ arkadaşlık bağı bulunan bir örnek kurmuş olduk.

En az $43$ arkadaşlık bağı gerektiğini ise tümevarım ile gösterebiliriz. İddiamız şudur ki; her $n>1$ tam sayısı için gereken arkadaşlık bağı sayısı $2n-3$ tür. $n=2$ iken $1$ arkadaşlık bağı bulunması gerektiği açıktır, aksi takdirde iki öğrenciyi aynı veya farklı gruba koyabiliriz ki tek türlü dağıtmış olmayız. $n=k$ iken dağıtabilmemiz için $2k-3$ bağ gerekiyor olsun. $k+1$ öğrenciyi dağıttığımızda ilk $k$ öğrenciyi tek türlü dağıtabilmek için $2k-3$ bağ gerekecek, $k+1.$ öğrencinin tek türlü gidişini sağlamak için iki bağ daha gerekecek ve toplam $2k-1=2(k+1)-3$ bağ gerekecektir, ispat bitmiştir.

(Şöyle de düşünebiliriz ki; eğer $2n-2$ arkadaşlık bağı ile öğrencileri dağıtabilseydik öğrencilerden birini çıkardığımızda geriye en az $2n-3$ arkadaşlık bağı kalması gerekeceğinden bu öğrencinin en fazla $1$ arkadaşlık bağı bulunabileceğini söyleyebilirdik, ki bu durumda da bu öğrenci arkadaşlık bağı bulunmayan iki gruba da gidebilirdi, çelişki.)
« Son Düzenleme: Temmuz 03, 2015, 02:31:57 ös Gönderen: ERhan ERdoğan »
delirttiniz lan beni

 


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