Altı Kişi {Çözüldü}

[senior]

Altı kişilik bir grupta, herkesin birbirini tanıdığı 3 kişi veya hiçkimsenin birbirini tanımadığı 3 kişi seçmenin her zaman mümkün olduğunu gösteriniz. (Soruda tanımak karşılıklı algılanmalı, eğer A kişisi B yi tanıyor ise, aynı şekilde B de A yı tanıyor demektir. )

[çılgın]

Bir $A$ kişisi alalım. Bu $A$ kişisi kalan $5$ kişiden ya en az $3$ kişiyi tanımaktadır, ya da en az $3$ kişiyi tanımamaktadır. Varsayalım ilki olsun (simetrik olduğu kolayca görülebilir). $A$ nın tanıdığı kişiler $B,C,D$ olsun. bu üç kişiden bir ikili tanışık olur ise -varsayalım $B$ ile $C$ olsun- $A,B,C$ üçlüsünde herkes birbirini tanır. bu üç kişiden bir ikili tanışık değil ise $B,C,D$ üçlüsünde kimse birbirini tanımaz.

[Lokman Gökçe]

Soru, Ramsey Problemi olarak bilinir. Şunu da soralım:

$n$ kişi arasında ya birbirini tanıyan $3$ kişilik bir grup, ya da herhangi ikisinin birbirini tanımadığı $3$ kişilik bir grup bulunabilmesini garanti etmek için gerekli en küçük $n$ pozitif tamsayısı nedir?

İpucu: $n=6$ kişiyle garanti edilebildiğini yukarıdaki çözümde gördük. $n=5$ kişi için de aynı özellik sağlanır mı, yoksa bir ters örnek var mıdır? Bunu araştırmalısınız.

[Lokman Gökçe]

$n=5$ durumuna ters örnek vardır. Beşgenin köşe noktaları beş kişiyi temsil etsin. İki nokta arasındaki kırmızı çizgi, iki kişinin birbirini tanıdığını göstersin. İki nokta arasındaki mavi çizgi ise, iki kişinin birbirini tanımadığını göstersin. Bu halde tüm kenarları aynı renkli üçgen bulunmadığından $n=5$ kişi ile istenen durum garanti edilemez. $n=6$ sayısı aranan özellikteki en küçük sayıdır.