C-Tabara MATHTIME-Jupiter.ziua5.ex6

C-Tabara MATHTIME-Jupiter.ziua5.ex6

Mesajde Iman » Sâm Sep 03, 2011 7:07 pm

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?
Avatar utilizator
Iman
 
Mesaje: 51
Membru din: Mar Noi 16, 2010 9:51 pm
Localitate: Constanta

Re: C-Tabara MATHTIME-Jupiter.ziua5.ex6

Mesajde Laurențiu Ploscaru » Lun Sep 05, 2011 8:57 pm

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.
Avatar utilizator
Laurențiu Ploscaru
 
Mesaje: 1237
Membru din: Mie Mai 04, 2011 5:42 pm
Localitate: Călimănești

Re: C-Tabara MATHTIME-Jupiter.ziua5.ex6

Mesajde drytime » Joi Sep 08, 2011 2:53 pm

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]).
drytime
 
Mesaje: 183
Membru din: Lun Iul 19, 2010 4:56 pm


Înapoi la Combinatorica

Cine este conectat

Utilizatorii ce navighează pe acest forum: Niciun utilizator înregistrat şi 1 vizitator

cron