Matematyczna zasada gołębich gniazd - "Wiedzą, co mówią" odc. 4.

W ramach cyklu „Wiedzą, co mówią” dr inż. Jakub Szczepaniak z Centrum Nauczania Matematyki i Fizyki PŁ wyjaśnia działanie tzw. zasady gołębich gniazd, określanej też mianem zasady szufladkowej.

Sformułowanie to pojawiło się po raz pierwszy w roku 1834, w pracy niemieckiego matematyka Petera Gustava Dirichleta.

Aby je zrozumieć, wyobraźmy sobie sytuację, gdy gołębie lecą ku gniazdom, których jest mniej niż ptaków. Po ich wylądowaniu okaże się, że w co najmniej jednym gnieździe wyląduje więcej niż jeden gołąb. Tylko tyle i aż tyle.

Bezpośrednio z tej zasady wynika bezsporny wniosek, że jeżeli spotka się 8 osób, to co najmniej dwie z nich urodziły się w tym samym dniu tygodnia.

A teraz bardzo aktualne zastosowanie zasady gołębich gniazd.

W sobotę, 28 października 2017 r. na Politechnice Łódzkiej, w Zatoce Sportu zorganizowano bal, aby hucznie uczcić 25-lecie Centrum Kształcenia Międzynarodowego (IFE).

Ostrożne szacunki mówią o 600 osobach obecnych na balu. Wykażemy, korzystając z zasady gołębich gniazd, że wśród gości znalazły się co najmniej dwie osoby mające tyle samo znajomych obecnych na balu. Oczywiście zakładamy, że relacja znajomości jest symetryczna, gdy osoba A zna osobę B, to również osoba B zna osobę A.

Przyjmijmy, że gołębiami będą goście obecni na balu. Mamy zatem 600 gołębi. Gniazda to możliwe liczby znajomych, których można spotkać na balu. Pozornie tych gniazd może być też 600. Odpowiadają one liczbom:

• 0 – ktoś nie zna nikogo,
• 1- ktoś zna jedną osobę,
• 2 – ktoś zna dwie osoby
• i tak dalej, aż do 599 – ktoś zna wszystkich obecnych na balu.

Ale przecież na liście gniazd nie mogą pojawić się jednocześnie 0 oraz 599. Niemożliwe, aby istniały takie dwie osoby, z których jedna z nich zna wszystkich obecnych, a druga nie zna nikogo. Jeśli istnieje osoba, która zna wszystkich, to nie istnieje osoba, która nie zna nikogo i odwrotnie. Zatem chociażby z tego powodu gniazd jest 599, a gołębi 600.

Musi się znaleźć co najmniej jedno gniazdo z dwoma gołębiami wewnątrz. Na Gali IFE były obecne co najmniej dwie osoby mające taką sama liczbę znajomych bawiących się wraz z nimi na tym historycznym już zapewne balu.