kombinatorik

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.

n=1 için sağlanması her n değeri için sağlanacağını göstermez ki.

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ı x_i , y okulundaki tanıdık sayısı y_i olsun, (x_i+y_i=n+1)
bu durumda her i için x_i lerin y_i leri oluşturanlarla tanışıklığı olamaz (aksi halde üçlü oluşurdu)
öyleyse
∑x_i.y_i 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²-∑x_i.y_i≥n.(n+1)/2 olmalıdır
bu da her i için x_i, y_i≥1 ve sonucunda x_i.y_i≥n olduğundan mümkün değildir.


çözüm uzun gibi duruyor ama düzenlerseniz fazla uzun olmadığı görülecektir.

Teşekkür ederim öğretmenim, Anladım.