Kaynak istiyor 21 öğrenciden oluşan bir sınıfta bazı öğrenciler arkadaştır (arkadaşlık karşılıklıdır). Bu sınıfta arkadaş sayıları eşit olan iki arkadaş bulunmuyorsa, bu sınıftaki arkadaş ikililerinin sayısı en fazla kaç olabilir?

Cevap 175

Sorunun püf noktası,

”aynı arkadaş sayısına sahip öğrenci bulunamaz” demiyor, “aynı arkadaş sayısına sahip arkadaş bulunamaz”(1) diyor. Şimdi maksimumdan bakalım, birisinin maksimum kaç arkadaşı olabilir? Kendisini saymadığımız için . Öğrencileri olarak sıralarsak genelliği bozmadan

, arkadaşa sahip olsun diyebiliriz.

bütün herkesle arkadaş olduğu için bir tane daha arkadaşa sahip birisi ekleyemeyiz yoksa (1) ile çelişiriz. Bundan ötürü ’den sonra en çok arkadaşı olan kişi arkadaşa sahip olabilir.

, arkadaşa sahip olsun diyebiliriz.(ile arkadaş, ve kendisini çıkarınca kalan isimden ’iyle arkadaş -> biri hariç herkesle arkadaş)

Bundan sonra da maksimuma oynayacağımız için arkadaşı olan birisi daha olabilir mi diye bakıyoruz, ’nin arkadaş olmadığı birisi var. O halde

, arkadaşa sahip olsun ve ile arkadaş olmasın diyebiliriz.

için arkadaş mümkün değil, arkadaşa sahip kişi olsaydı güvercin yuvası ilkesinden ötürü zaten ’ü içinde en az bir arkadaş çifti olucağını görebilirsiniz. Başka bir deyişle, kişinin arkadaşı olucaksa edecektir ve olduğundan çelişki olacaktır ve ’lü kendi içinde de arkadaş çifti barındıracaktır -ki bu (1) ile çelişir-.

O halde , kişiyle arkadaş olacaktır.

Benzer bir düşünceyle olduğu için tane kişiyle arkadaş olup kendi içinde arkadaş olmayan kişi bulunabileceğini gözlemleyebilirsin

, , birbirleriyle arkadaş olmayıp diğer herkesle arkadaş( kişi) olan öğrenci üçlüsüdür.

Örüntüyü yakalamışsınızdır sanıyorum, teyit edebilirsiniz ama kısaca: maksimumu aradığımız noktada,

arkadaşa sahip olacaktır. Bu da,

bağ demektir. Her öğrencinin arkadaş sayısını ayrı saydığımız için her arkadaşlık bağında tekrara düştüğümüzü fark edin isterim. Mesela ve ’nin arkadaşlığı hem ’de bahsi geçen kişide geçti hem de ’de bahsi geçen kişide. O halde her arkadaşlık bağı ’şer kez tekrara düştüğünden bize farklı arkadaş çift sayısını verir ki bu da cevaptır.

Buraya bu durumu sağlayan bir graf koyuyorum, sevgili Evrim Ağacı yetkilileri, graf çizmeyi bilmediğimden ötürü grafı yapay zekaya yaptırdım yoksa çözüm fikri ve metni bariz biçimde bana aittir.

OpenAI