Zasada szufladkowa Dirichleta

[Piotr39]

W spotkaniu Koła młodych matematyków wzięło udział 20 uczniów. Okazało się, że wśród każdych czterech uczestników spotkania był co najmniej jeden uczestnik, który znał pozostałych trzech uczniów z tej czwórki. Udowodnić, że wśród uczestników Koła jest uczeń, który zna wszystkich pozostałych uczestników Koła.

[grdv10]

Przypuśćmy nie wprost, że istnieje czwórka uczniów, w której każdy uczeń zna co najwyżej dwóch uczniów. Zanalizuj, co by z tego wynikło...

Trzeba by dojść do sprzeczności. Albo - przez kontrapozycję - pokazać, że w takiej sytuacji znajdziemy ucznia, który nie zna wszystkich uczestników koła.