C-Tabara MATHTIME-Jupiter.ziua5.ex6

[Iman]

Avem $$ n $$ puncte in plan,oricare $$2$$ sunt unite printr-un segment,iar oricare $$3$$ necoliniare.Toate segmentele sunt colorate in $$4$$ culori.Care este valoarea minima a lui $$ n $$ pentru care exista un triunghi monocolor cu varfurile in aceste puncte?

[Laurențiu Ploscaru]

Iese imediat cu Teorema lui Ramsey (grafuri).

[drytime]

Acum ca m-am documentat pot spune destul de sigur ca Iman a scris problema gresit. Teorema lui Ramsey afirma doar faptul ca acel $n$ exista. Demonstratia teoremei (cel putin cea pe care eu o stiu) ofera si un majorant pentru $n$, dar care e in general slab (nu neaparat ca magnitudine, dar rateaza numarul cu cateva unitati). Aici e un articol de 12 pagini in care tot ce arata este ca $n$ este cel mult 62.(articolul acesta e chiar scurt; am gasit unul cu vreo 100 de pagini). Nu se spune nimic de faptul ca s-ar putea sa existe model cu 61 de puncte ce nu are triunghi monocromatic. In cazul in care se folosesc 3 culori, n=17; vezi aici. Poate in problema trebuie aratat ca n este cel mult 66. (demonstratia aici nu e foarte grea; luam un punct si din el pleaca cel putin 17 muchii de aceeasi culoare; daca nu avem triunghi monocromatic cele 17 puncte au intre ele doar segmente de celelalte 3 culori. din astea 17 luam unul, iar din el vor pleca cel putin 6 segmente de aceeasi culoare. aceste 6 puncte nu au intre ele segmente de aceasta a doua culoare dar nici de prima culoare, deci au una din celelalte 2 culori. luam unul din cele 6 pct, iar din el vor pleca cel putin 3 segmente de aceeasi culoare. aceste trei puncte pot fi uniote doar cu ultima culoare, deci avem triunghiul. Am folosit la greu principiul cutiei; evident rezultatul se poate generaliza [vezi Engel]).