Logicus - Antrenamentul conexiunilor rapide

Într-un grup de 17 prieteni constituit pe una din rețelele de socializare de pe internet, există doar trei subiecte de discuție. Oricare doi prieteni din acest grup discută doar despre un singur subiect. Să se arate că cel puțin trei prieteni din acest grup discută între ei despre același subiect.
(După o problemă propusă la Olimpiada Internațională de Matematică, Moscova, 1964)

Soluție:

Fie A un prieten oarecare din grupul celor 17. El trebuie să aibă un subiect comun a de discuție cu cel puțin 6 din ceilalți prieteni (fie aceștia B, C, D, E, F și G.) Într-adevăr, dacă pe fiecare temă ar discuta cu cel mult 5 prieteni, atunci pe cele trei teme el nu ar discuta cu mai mult de 15 prieteni, nemaiavând subiecte de discuție cu al șaptesprezecelea, ceea ce ar contrazice condițiile din enunț.
Dacă printre prietenii B, C, D, E, F și G se găsesc doi (de exemplu B și C) care discută despre subiectul a, demonstrația este încheiată, grupul celor 3 prieteni care discută între ei despre același subiect fiind A, B și C.
Dacă B nu discută cu niciunul dintre prietenii C, D, E, F sau G despre subiectul a, atunci el trebuie să discute despre subiectul b sau c și anume cu cel puțin trei (D, E, F de exemplu) despre un subiect (b, de exemplu), căci dacă ar discuta asupra fiecărui subiect cu cel mult 2 prieteni, nu ar mai avea subiect de discuție cu cel puțin un alt prieten.
Dacă printre prietenii D, E și F există 2 (de exemplu D și E) care să discute tot asupra subiectului b, a fost de asemenea găsit grupul de prieteni căutat: B, D și E.
Dacă însă D, E și F nu discută între ei asupra subiectului b, ei trebuie să discute asupra subiectului c și astfel grupul de trei prieteni este de asemenea determinat: D, E și F.
Întrucât au fost analizate toate cazurile posibile, demonstrația afirmației din enunț este încheiată.

• Prec
• Mai departe