C(2n,n) kişilik bir grup içinden herkesin birbirini tanıdığı ya da kimsenin birbirini tanımadığı n+1 kişilik bir grup seçilebileceğini kanıtlayınız.
C(2n,n) kişilik bir grup içinden herkesin birbirini tanıdığı ya da kimsenin birbirini tanımadığı n+1 kişilik bir grup seçilebileceğini kanıtlayınız.
Ramsey kuramı yada Ramsey sayıları wikipedia da arayın
biraz araştırdım sanırım soru bizden r(n+1,n+1)=C(2n,n) olduğunu göstermemizi istiyor bir de
r(a,b) ≤ r(a − 1,b) + r(a,b − 1) diye bir eşitsizlik vermiş işe yarar mı?
N kişilik bir gruptan birbirini tanıyan a kişi yada birbirlerini tanımayan b kişi seçilir buda R(a,b) ramsey sayıları
R(a,b)≤ (a+b-2 , a-1) eşitsizşliğini sağlar
eğer a=b=n+1 alırsanız
R(n+1,n+1)≤(2n,n)
Foruma üye olmana gerek yok! Facebook hesabınla yorumlarını bekliyoruz!