Ödüllü Soru 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?

Sonuç Korkunç!

Fakat soru cidden çok özel ve güzel...

Anladığım kadarıyla:

Soruda her ne kadar ve çeldirici olarak " Bazı öğrenciler arkadaştır" ifadesi geçse de, devamındaki sınırlayıcı ifadeler nedeni ile diyebilirim ki; 30 yıllık öğretmenlik hayatım boyunca böyle bir sınıfa tanık olmadım.

Temenni ederim ki bundan sonra da, hiç kimsenin hiç kimse ile arkadaş olmadığı bir sınıfa tanık olmam. Sevgiyle...

21 kişilik sınıfta herkes ile arkadaş olan 20 arkadaşı olan sadece bir öğrenci olabilir arkadaşların arkadaş sayısının eşit olmaması içinde 19 arkadaş olan 2 öğrenci birbiri ile arkadaş değildir bu 2 19 arkadaşı olan öğrencilerin 20 arkadaşı olan öğrenciden farklı 18 arkadaşlık ilişkileri bulunmaktadır. Bu şekilde bir örüntü kurarak^[1][1] aşağıdaki cevabı bulabiliriz.

Arkadaşlık ilişkileri eşit arkadaşlar olmaması için arkadaşlık ilişki sayısı eşit olan ama birbirleri ile arkadaş olmayan gruplar oluşması gerektiğini düşünüyorum.

20+(2*18)+(3*16)+(4*14)+(5*12)+(6*10)=280 cevabını bulabiliriz.

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