|
[quote="grossi"]Koliko je najmanje ljudi potrebno biti u drustvo da imamo troje ljudi koji se medjusobno poznaju ili troje ljudi koji se medjusobno ne poznaju?
Taj problem je ekvivalentan pitanju R(3,3;2)=?
Odgovor je naravno 6. To je čak lako i dokazati.
Moje pitanje je sljedece, ako imam npr.
R(4,5,2;3)=?
ili
R(3,5;4)=?
Kako glasi ekvivalentan problem mom pitanju.
Hvala.[/quote]
R(m1,m2,...,mk;n) je najmanji broj elemenata u skupu u kojem, kad promatramo skup svih njegovih n-članih podskupova i svakog od njih bojamo u jednu od k bojâ b1,b2,...,bk , uvijek će postojati neka boja bi u koju će biti obojani svi podskupovi nekog mi-članog skupa.
Dakle, R(4,5,2;3) je najmanji broj r takav da ako u skupu [1..r] sve tročlane podskupove (ima ih r povrh 3 ) bojamo u crvenu, zelenu ili plavu boju, uvijek postoje ili 4 elementa (među tih [1..r] ) čiji su svi tročlani podskupovi (njih 4 ) obojeni crveno, ili 5 elemenata među [1..r] čije su sve trojke zelene, ili 2 elementa čije su sve trojke plave.
(Inače, takav broj je očito 2 , jer ne moraš ništa bojati, i uvijek postoje (ta) dva elementa čije su sve trojke (jer ih nema) plave.)
R(3,5;4) je najmanji r takav da kad svaki od (r povrh 4) 4članih podskupova od [1..r] obojamo u crvenu illi plavu boju (ekvivalentno, razdijelimo ih u dvije grupe - s tim da znamo koja je koja), sigurno postoje 3 elementa čije su sve četvorke crvene, ili 5 elemenata čije su sve četvorke plave.
(Naravno, kao i gore, zbog 3<4 , taj broj je 3 . Zaključujemo da su Ramseyevi brojevi prilično trivijalni ako (Ei@[1..k])(mi<n) . :-) )
Prvi navedeni problem je R(3,3;2)=6 , jer među 6 ljudi či (,i@[1..6]), ako svaki par ljudi "obojamo" u jednu od dvije boje "poznaju se" ili "ne poznaju se", uvijek postoje ili 3 para koja su obojena "poznavanjem" ili 3 para koja su obojena "nepoznavanjem".
ok?
| grossi (napisa): | Koliko je najmanje ljudi potrebno biti u drustvo da imamo troje ljudi koji se medjusobno poznaju ili troje ljudi koji se medjusobno ne poznaju?
Taj problem je ekvivalentan pitanju R(3,3;2)=?
Odgovor je naravno 6. To je čak lako i dokazati.
Moje pitanje je sljedece, ako imam npr.
R(4,5,2;3)=?
ili
R(3,5;4)=?
Kako glasi ekvivalentan problem mom pitanju.
Hvala. |
R(m1,m2,...,mk;n) je najmanji broj elemenata u skupu u kojem, kad promatramo skup svih njegovih n-članih podskupova i svakog od njih bojamo u jednu od k bojâ b1,b2,...,bk , uvijek će postojati neka boja bi u koju će biti obojani svi podskupovi nekog mi-članog skupa.
Dakle, R(4,5,2;3) je najmanji broj r takav da ako u skupu [1..r] sve tročlane podskupove (ima ih r povrh 3 ) bojamo u crvenu, zelenu ili plavu boju, uvijek postoje ili 4 elementa (među tih [1..r] ) čiji su svi tročlani podskupovi (njih 4 ) obojeni crveno, ili 5 elemenata među [1..r] čije su sve trojke zelene, ili 2 elementa čije su sve trojke plave.
(Inače, takav broj je očito 2 , jer ne moraš ništa bojati, i uvijek postoje (ta) dva elementa čije su sve trojke (jer ih nema) plave.)
R(3,5;4) je najmanji r takav da kad svaki od (r povrh 4) 4članih podskupova od [1..r] obojamo u crvenu illi plavu boju (ekvivalentno, razdijelimo ih u dvije grupe - s tim da znamo koja je koja), sigurno postoje 3 elementa čije su sve četvorke crvene, ili 5 elemenata čije su sve četvorke plave.
(Naravno, kao i gore, zbog 3<4 , taj broj je 3 . Zaključujemo da su Ramseyevi brojevi prilično trivijalni ako (Ei@[1..k])(mi<n) .  )
Prvi navedeni problem je R(3,3;2)=6 , jer među 6 ljudi či (,i@[1..6]), ako svaki par ljudi "obojamo" u jednu od dvije boje "poznaju se" ili "ne poznaju se", uvijek postoje ili 3 para koja su obojena "poznavanjem" ili 3 para koja su obojena "nepoznavanjem".
ok?
|
