Bine aţi venit pe Scientia QA!
Pentru a putea publica întrebări şi răspunsuri, trebuie să vă înregistraţi.
Atenţie! Este posibil ca e-mailul de confirmare a înregistrării să intre în Spam.
Pune o întrebare

Newsletter


3.5k intrebari

6.7k raspunsuri

15.2k comentarii

2.2k utilizatori

0 plusuri 0 minusuri
320 vizualizari

La o serată de 10 persoane, din oricare grup de trei persoane sînt cel puţin două persoane care nu se cunosc între ele. Să se arate că la această serată există patru persoane care nu se cunosc între ele.

Experimentat (4.8k puncte) in categoria Matematica

2 Raspunsuri

1 plus 0 minusuri
 
Cel mai bun raspuns
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.
Experimentat (2.3k puncte)
selectat de
0 0

Referitor la soluţii, parafrazez un mic poet al cărui vers descrie cel mai bine starea mea de percepţie a rezolvării oferite de maiestatea dvs. : "Vai, ce ceaţă deasă, nu mai găsesc drumul spre casă, domnul profesor".

0 0
E bine si ma bucur ca ai comentat ceva la problema ,sincer ma asteptam la mai multe comentarii sau intrebari si din partea altora.Dupa cum se vede ,problema depaseste cu mult nivelul de liceu si e mai apropiata de olimpiada internationala.Dar din cauza ca ideea de rezolvare e ca un drum cu sens unic fara prea multe sanse de solutii diversificate ,aceasta problema ar fi sigur respinsa.Totusi e o problema pregatitoare unui gen de nivel OIM.

Pe alta parte eu m-am straduit sa o fac sa fie cat mai lesne de inteles,avand in vedere ca folosesc destul de multe notiuni cvasinecunoscute multora.O alta dificultate e lipsa de editare tex pe QA in timp ce pe forum e posibil.
0 0
Intuiţia îmi dictează că există şi o soluţie mai "umană", accesibilă şi nouă. Sper să apar cu ea, termen maxim un an, între timp studiez limba română pentru a-mi lua un doctorat. Forumul de pe acest site este zero. Nu am găsit absolut nimic interesant, ba dimpotrivă mă bătea gîndul să trec printr-un fel de purgatoriu după ce am citit una alta de pe acolo, e drept că participanţii din zona respectivă erau inocenţi faţă de alţii de pe alte site-uri obscure din această ţară la care am participat din naivitate.
0 0

Între timp, am stat şi m-am tot gîndit la o soluţie pentru acestă problemă, nu mi-a picat niciuna din cer, nu m-au ajutat nici cei nouă vecini pe care i-am chemat şi ordonat cum am vrut eu ca să găsesc o soluţie. Sper că altădată să prezentaţi soluţiile mai limpede, m-am prins greu de demonstraţia dvs. Felicitări.

0 plusuri 0 minusuri
Cateva observatii la solutia precedenta.

La aplicarea principiului includeri si excluderii .

A(y1) respectiv A(y2) si A(y3) au cel putin 7 muchii deci ele au un cardinal de forma 7+i,7+j respectiv 7+k unde i,j,k pot avea valorile 0,1 sau 2,deoarece maximul de muchi ce pleaca dintrun varf este 9.Intersectiile de 2 dintre ele in acest caz vor avea cel putin(adica <=)

7+i+7+j-10=4+i+j respectiv 4+i+k si 4+j+k.

Astfel intersectia tuturor 3 va avea cel putin 10-7-i-7-j-7-k+4+i+k+4+i+j+4+j+k=1+i+j+k elemente.

Totusi cred ca era mai simplu daca aratam ca in @G exista un varf de grad 4,dar tot nu e asa de simplu cat pare:)
Experimentat (2.3k puncte)
...