Teoria lui Ramsey
Teoria lui Ramsey, numită astfel după matematicianul englez Frank P. Ramsey (1903-1930), este o parte importantă a combinatoricii care se ocupă de distribuția submulțimilor de elemente ale unei mulțimi.
Exemplu
modificareEnunț
modificareSă presupunem că într-un grup de șase persoane, fiecare două persoane sunt fie prieteni, fie dușmani. Să se arate că în grup există fie trei persoane care sunt toate prietene între ele, fie trei persoane care se dușmănesc toate între ele.
Soluție
modificareFie A una dintre cele șase persoane. Între celelalte cinci persoane din grup :
(1) ori există trei sau mai multe care sunt toate prietene cu A,
(2) ori există trei sau mai multe care se dușmănesc toate cu A.
Acestă situație rezultă din principiul lui Dirichet generalizat, pentru că dacă cinci obiecte sunt împărțite în două grupe, una dintre grupe are cel puțin [5/2] = 3 obiecte.
În primul caz, să presupunem că B, C și D sunt prieteni cu A. Dacă există două dintre B,C și D care sunt prietene între ele, atunci acestea două împreună cu A formează grupul cerut de trei persoane - toate prietene între ele. Dacă nu există nici o prietenie în grupul B,C,D, am obținut un grup de trei persoane care se dușmănesc toate între ele.
Al doilea caz se tratează similar.
Notație : prin [m/n] se înțelege aici cel mai mare număr întreg mai mic decât m/n adică partea întreagă a lui m/n.
Generalizare
modificareNumărul lui Ramsey, R(m,n) unde m și n sunt numere întregi mai mari sau egale cu 2, indică numărul minim de persoane la o petrecere, astfel încît fi să existe un grup de m prieteni toți între ei, fie să existe un grup de n dușmani, toți între ei. Exemplul de mai sus arată că R(3,3)≤ 6. (În fapt, R(3,3)= 6).
Pentru m și n mici, numerele lui Ramsey sunt cunoscute.
2 3 4 5 6 7 ...
3 6 9 14 18 ...
4 9 18 25 ? ...
5 14 25 ? ...
Bibliografie
modificareKenneth H. Rosen, Discrete Mathematics and its Applications, Sixth Edition, McGraw-Hill, 2007