Her birinde n tane öğrenci olan üç okul vardır.Her öğrencinin diğer iki okulda tanıdığı n+1 tane öğrenci olduğuna göre, her biri farklı okullarda birbirini tanıyan üç öğrencinin varlığını gösteriniz.
Her birinde n tane öğrenci olan üç okul vardır.Her öğrencinin diğer iki okulda tanıdığı n+1 tane öğrenci olduğuna göre, her biri farklı okullarda birbirini tanıyan üç öğrencinin varlığını gösteriniz.
n tane dediğine göre, bu durum her değer için sağlanıyor demektir. n'ye 1 verirsek her okulda bir öğrenci olmuş olur. Bu durumda 1 öğrencinin diğer okullardan 2 öğrenci tanıması zorunlu hale gelir. Bu koşul, diğer öğrenciler içinde gerekli olduğundan hepsi birbirini tanıyacaktır. Öyleyse, birbirini tanıyan üç öğrenci, bu şartın sağlanabilmesi için var olmak zorundadır.
Haklısınız, ben sorunun soruluşuna göre n değerinin önemsiz olduğunu düşünmüştüm. Ama bizden istenen şey bu durumun varlığını göstermek değil mi? n=1 için bu durumun varlığı görülür. Ve her n değeri için varlığını ispat etmek gerekmeyebilir.
öncelikle tanışıklığın karşılıklı olduğunu varsayıyorum , A kişisi B kişisinin tanıyorsa B kişisi de A kişisini tanıyor diyoruz.
okullardaki öğrencilerin toplam 3n.(n+1)/2 tanışıklığı vardır (tokalaşma gibi düşünürsek tokalaşma sayısı)
şimdi soruda istenenin olmadığını düşünelim
okulları x,y ve z olarak adlandırsak
z okulundaki öğrencileri ele alalım , bunlar x ve y okulundaki öğrencilerle toplam (n+1).n tane tanışıklık oluştururlar
tüm tanışıklıklardan geriye kalan 3n.(n+1)/2-n.(n+1)=n.(n+1)/2 tanışıklık x ve y okulları arasındaki öğrenciler arasında olmalıdır.
z okulundaki i numaralı öğrencinin x okulundaki tanıdık sayısı xi , y okulundaki tanıdık sayısı yi olsun, (xi+yi=n+1)
bu durumda her i için xi lerin yi leri oluşturanlarla tanışıklığı olamaz (aksi halde üçlü oluşurdu)
öyleyse
∑xi.yi tane tanışıklık devre dışı kalır
x ile y okulları arasında oluşacak max tanışıklık sayısı n² dir
n²-∑xi.yi≥n.(n+1)/2 olmalıdır
bu da her i için xi, yi≥1 ve sonucunda xi.yi≥n olduğundan mümkün değildir.
çözüm uzun gibi duruyor ama düzenlerseniz fazla uzun olmadığı görülecektir.
Foruma üye olmana gerek yok! Facebook hesabınla yorumlarını bekliyoruz!