Logicus - Antrenamentul conexiunilor rapide

Congresul internațional al logicienilor de la Paris din aceste zile se bucură de prezența a n persoane (n > 2). Să se arate că printre participanți se găsesc 2 persoane care au același număr de cunoscuți printre cei prezenți (se presupune că dacă A este cunoscut al lui B, atunci și B este cunoscut al lui A; de asemenea, nimeni nu este considerat ca fiind cunoscut al lui însuși.)
(după o problemă propusă de Polonia la Olimpiada Internațională de Matematică)

Soluție:

Dacă numărul participanților la congres care nu au niciun cunoscut printre cei prezenți (și care din această cauză nu sunt ei înșiși cunoscuți de nimeni) este mai mare sau egal cu 2, afirmația din enunț este demonstrată.
Dacă numărul participanților care nu cunosc pe nimeni este mai mic decât 2 (0 sau 1), numărul celor care cunosc cel puțin un participant la congres este mai mare sau egal cu 2 (n > 2). Fie p numărul acestor persoane (care au cel puțin un cunoscut printre participanții la congres). Fiecare dintre aceste persoane poate avea 1, 2, 3, ... , p-1 cunoscuți; însă deoarece în total sunt doar p astfel de persoane, este evident că printre ele există cel puțin două care au același număr de cunoscuți. Q.E.D.

• Prec
• Mai departe