C-Tabara MATHTIME-Jupiter.ziua5.ex6
C-Tabara MATHTIME-Jupiter.ziua5.ex6
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
- Mesaje: 1237
- Membru din: Mie Mai 04, 2011 5:42 pm
- Localitate: Călimănești
- Contact:
Re: C-Tabara MATHTIME-Jupiter.ziua5.ex6
Iese imediat cu Teorema lui Ramsey (grafuri).
People are strange when you're a stranger,
Faces look ugly when you're alone.
Women seem wicked when you're unwanted,
Streets are uneven when you're down.
Faces look ugly when you're alone.
Women seem wicked when you're unwanted,
Streets are uneven when you're down.
Re: C-Tabara MATHTIME-Jupiter.ziua5.ex6
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]).