bgeorge

cei care aveau picioarele mai mari (adultii) au raspuns corect sau whatever... mai bine, iar cei cu picioarele mici (copii) se jucau cu batu-n nisip... :D

wmutex

Hmm... graful acela nu epuizeaza complet situatiile. Deci nu-i demonstratie exhaustiva. Problema spune doar ca, pentru un graf bicolor complet conex nu exista cicluri "monocolore" de dimensiune 3 pentru o anumita culoare, deci musai trebuie sa existe cicluri de dimensiune 3 pentru cealalta culoare.

Probabil ca algebric se rezolva mai elegant... dar inca nu am o solutie. Oops.

wmutex

Ok, pana la urma tot problema de grafuri ramane. Graful are drept noduri "stele de Holywood" (6 noduri) si drept muchii relatiile de apreciere reciproca intre ele (15 arce -- fiindca nici o "stea de Holywood" nu-i e indiferenta alteie). Graful e neorientat pentru ca, daca steaua1 o uraste pe steaua2 atunci si steaua2 o uraste pe steaua1 (la fel pentru iubire -- this is pukingly funny, by the way...)

Muchiile sunt colorate in negru pentru ura si in rosu pentru iubire (sa spunem -- important ca cele doua culori see fie diferite). Problema se reformuleaza astfel: daca in graf nu exista ciclu de dimensiune 3 de culoare neagra, sa se arate ca exista un ciclu de dimensiune 3 de culoare rosie.


Solutie: Cel mai intins posibil subgraf  de culoare neagra al grafului initial fara cicluri de dimensiune 3 are 7 muchii (si 2 cicluri de dimensiune 4). Mai exista un subgraf maximal (caruia nu i se poate agauga un arc in plus fara sa se incalce regula de constructie) cu un singur ciclu de dimensiune 5. Exemplele sunt in figura in figura.

Daca graful maximal negru fara cicluri de dimensiune 3 are maxim 7 muchii, dintre cele 15 mai raman cel putin 8 muchii rosii. Deci exista cel putin un ciclu de dimensiune 3 formate de cele 8 muchii rosii (pentru ca 8>7, desigur).

ixirimdi

O mica explicitare relativ la figura de la ora 14:

Problema se rezolva usor utilizand grafuri. Sase puncte (varfuri) resprezinta cei sase indivizi (stele). Toate varfurile sunt conectate cu toate celelalte prin linii intrerupte (arce) care reprezinta ori dragoste reciproca, ori ura reciproca. Liniile albastre simbolizeaza dragoste si liniile rosii ura.
Sa luam varful A. din cele 5 arce plecand din el, cel putin 3 trebuie sa fie de aceeasi culoare. Argumentul este acelasi indiferent ce culoare sau ce 3 linii alegem. Asa ca sa presupunem ca 3 linii sunt rosii (desenate cu negru in figura). Daca liniile ce formeaza triunghiul BCE sunt toate albastre atunci avem un set de 3 indivizi care se iubesc reciproc. Ni se spune ca un asemenea set un exista, prin urmare cel putin o latura a triunghiului este rosie. Indiferent ce latura alegem sa fie rosie, vom obtine un triunghi cu toate laturile rosii (adica 3 indivizi care se urasc reciproc)

Acelasi rezultat il obtinem daca alegem ca primele 3 arce ce pornesc din varful A sa fie albastre in loc de rosii. In acest caz cele 3 laturi ale triunghiului BCE trebuie sa fie rosii, in caz contrar, o latura albastra ar forma un triunghi albastru, corespunzand unui grup de 3 indivizi care se iubesc reciproc. Pe scurt trebuie sa fie cel putin un triunghi care are toate laturile ori albastre, ori rosii. Datele problemei spun ca nu poate exista un triunghi albastru, deci trebuie ca triunghiul sa fie rosu.
De fapt inca o concluzie se mai poate obtine. Daca nu exista nici un triunghi albastru, se poate demonstra (mai complicat) ca exista cel putin 2 triunghiuri rosii. In teoria grafurilor, un astfel de graf in 2 culori care nu are triunghiuri albastre se numeste un graf cromatic “albastru-gol”. (fara-albastru) Daca numarul de varfuri este 6, ca in aceasta problema, atunci numarul minim de triunghiuri rosii este 2.

Cand numarul de varfuri in un graf cromatic albastru-gol este mai mic de 6, este usor sa se construiasca astfel de grafu