Rezolvare:

Au trimis soluţii corecte: Aurel Ionescu, Zoltan Szabo, Ady Nicolae şi Viorel Manta

Soluţia 1 (Ady Nicolae, Aurel Ionescu):

Avem 20 de variante posibile pentru a forma din cei 6 persoane grupuri de căte 3:

1

1

2

3

2

1

2

4

3

1

2

5

4

1

2

6

5

1

3

4

6

1

3

5

7

1

3

6

8

1

4

5

9

1

4

6

10

1

5

6

11

2

3

4

12

2

3

5

13

2

3

6

14

2

4

5

15

2

4

6

16

2

5

6

17

3

4

5

18

3

4

6

19

3

5

6

20

4

5

6

 Cazul 1: Niciunul din cei 6 nu se cunosc între ei. Rezultă că nu putem avea niciun grup de 3 persoane în care toți să se cunoască între ei.

Cazul 2: Se cunosc între ei doar două personae, 1=2, idem ca mai sus.

Cazul 3: Trei persoane se cunosc între ele: 1=2=3.

Există subgrupul  1 din tabelul de mai sus în care toți 3 se cunosc între ei.

Cazul 4: Patru persoane se cunosc între ele: 1=2=3=4

Avem 4 subgrupuri de câte 3 persoane: 1, 2, 5, 11 din tabel, care se cunosc între ele.

 

Soluţia 2 (Szabo Zoltan):

Admitem că relaţia de cunoştinţă este simetrică, adică "Dacă X îl cunoaşte pe Y, atunci şi Y îl cunoaşte pe X."

Vom considera un graf neorientat, în care nodurile sunt cele 6 persoane, iar două noduri X şi Y sunt adiacente dacă şi numai dacă persoanele X şi Y se cunosc. 

Afirmaţia "există un subgrup de cel puţin trei persoane, în care toţi se cunosc între ei" este echivalentă că afirmaţia "graful conţine un subgraf complet de grad cel puţin 3". Dacă răspunsul este afirmativ, atunci avem răspuns pentru afirmaţia 1.

În cazul în care graful nu conţine niciun subgraf complet de 3 noduri, trebuie să demonstrăm, că este adevărată afirmaţia 2: "există un subgrup de cel puţin trei persoane, în care nimeni nu are pe cineva cunoscut". 

Cazuri posibile: 

1. Există un ciclu de lungime 5 şi încă un nod care poate fi izolat sau adiacent cu vreun nod al ciclului. În acest caz alegem acest nod pe care l-am pomenit ultima oară, şi din ciclul de lungime 5 alte două noduri care nu sunt adiacente nici între ele şi nici cu nodul ales anterior.

2. Nu există nici ciclu de lungime 3, nici ciclu de lungime 5. Î