Geomania.Org Forumları
Fantezi Cebir => Kombinatorik => Konuyu başlatan: senior - Ağustos 15, 2015, 10:17:22 öö
-
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. )
-
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.
-
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.
-
$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.