Problema saptamanii - Subgrupuri de 3 persoane (Solutie)

Andrei Grigorean
18 noiembrie 2009

Voi reformula problema in termeni de grafuri pentru a usura intelegerea explicatiei:

Se da un graf complet cu 6 noduri in care fiecare muchie este colorata sau in rosu, sau in albastru. Spunem ca un triplet de noduri (a, b, c) este monocromatic daca muchiile (a, b), (b, c) si (a, c) au acceasi culoare. Se cere sa se demonstreze ca exista cel putin 2 triplete monocromatice.

Solutia mea este urmatoarea: Numarul total de triplete este egal cu 20. Voi incerca sa demonstrez ca pot fi maxim 18 triplete care nu sunt monocromatice. Pentru a numara cate astfel de triplete sunt, putem sa folosim jmenul de la problema Color. Pentru fiecare nod vom inmulti numarul de muchii albastre incidente cu numarul de muchii rosii incidente. Adunand aceste valori si impartind la 2, obtinem numarul de triplete nemonocromatice. Va voi lasa pe voi sa demonstrati aceasta afirmatie :P. Numarul maxim de triplete nemonocromatice se obtine atunci cand pentru fiecare nod in parte produsul dintre numarul de muchii albastre si rosii este cat mai mare. Cum gradul unui nod este egal cu 5, rezulta ca produsul poate fi maxim 6. Deci, numarul maxim de triplete ce nu sunt monocromatice este 6 * 6 / 2 = 18.

Rezolvarea poate fi generalizata pentru grafuri mari.

Solutii corecte constructive au fost oferite de: Alex Mosoi, Andrei Dragus, Daniel Anghel.