Aceasta problema e frumoasa dar si foarte grea.
Ea se rezolva cu ajutorul grafurilor.Pentru cei ce nu cunosc ce este un graf am sa prezint cateva definitii.
Se numeste graf o multime de varfuri impreuna cu o multime de muchii ce unesc varfuri .De obicei notam cu G grafurile V varfurile si U multimea muchiilor si scriem
G=(V;U)
Se numeste subgraf o submultime din multimea V si contine muchiile din U cu varfurile din submultime.
Se numeste graf complet un graf in care oricare 2 varfuri sunt unite de o muchie.
Se numeste gradul unui varf x numarul de muchii distincte ce contin varful x si o sa il notam cu d(x)
Mai exista foarte multe notiuni precum ciclu,drum,drum hamiltonian,conexitate,graf orientat,graf k-regulat etc. dar nu fac un curs de teoria grafurilor acuma.
Pentru problema noastra o sa consideram cele 10 persoane ca fiind varfuri si o sa formam 2 grafuri unul cu muchii daca persoana i si j nu se cunoaste si altul care va fi un graf complementar cu muchie daca persoana i si j se cunoaste.O sa le notam cu G si @G.
Vom presupune prin absurd ca nu exista 4 persoane care nu se cunosc adica in graful G ca nu exista subgrafuri complete de 4 varfuri si vom arata ca asta implica un subgraf complet in @G de 3 varfuri (adica gasim 3 persoane care se cunosc intre ele)ceea ce contrazice ipoteza.
Vom demonstra ca in graful G exista cel putin 3 varfuri cu grade mai mici sau egale cu 6.
Sa presupunem prin absurd ca multimea X a varfurilor cu grade <=6 are mai putin de 3 varfuri adica |X|<3 atunci multimea Y a varfurilor cu grade mai mari ca 6 ar avea cel putin 8 varfuri.Mai exact |Y|>10-3=7.
Alegem un varf din Y fie y1 si consideram multimea A(y1) formata din varfurile adiacente cu y1(adica sunt legate cu o muchie de y1) si cum elementele din Y au grad cel putin 7 inseamna ca avem A(y1)>=7 asta inseamna ca putem lua un element y2 din A(y1) care sa nu fie in X.
Dar A(y1) intersectat cu A(y2) va avea cel putin 7+7-10 varfuri=4 varfuri deci putem alege un varf y3 din intersectie care sa nu fie in X.Dar A(y1) intersectat cu A(y2) si cu A(y3) au cel putin un element deoarece cardinalul satisface inegalitatea
>=10-7-7-7+4+4+4=1(Principiul includeri si excluderi) deci putem lua un varf y4 din intersectie si asta inseamna ca y1,y2,y3 si y4 formeaza un subgraf complet ceea ce este o contradictie.
Revin mai tz cu continuarea solutiei.Ideea e ca acuma stim ca @G are cel putin 3 varfuri cu grade mai mari ca 4 .
Acuma continuarea.Deci conform problemei precedente un graf ce nu contine subgrafuri complete de 4 varfuri admite cel putin 3 varfuri de grade mai mici sau egale cu 6 ,asta inseamna ca in graful complementar avem cel putin 3 varfuri de grad 10-6=4.Fie x1 unul din varfuri din care pleaca 4 muchii si atunci sa zicem la cele 4 varfuri cu care se uneste a,b,c,d ,dar cele 4 varfuri a,b,c,d trebuie sa aiba cel putin o muchie conform presupuneri noastre ca orice grup de 4 sunt 2 care se cunosc .atunci varful x1 impreuna cu cele ce formeaza aceasta muchie determina un triunghi si astfel am obtinut contradictia.
Sincer am stat ceva sa ma gandesc la ea si stiu ca nu e deloc o solutie simpla asta .Dar nici nu cred ca alte solutii ar fi mai simple,din contra una bazata pe enumerare ar fi foarte greu de prezentat.
