Zasada gołębiej dziury

2010-06-10 19:42

Dzisiejsza notka będzie o pewnej matematycznej ciekawostce, która pokazuje, że nawet pozornie oczywiste stwierdzenie mogą mieć daleko idące konsekwencje, jakich nie da się na pierwszy rzut oka przewidzieć. Mamy mianowicie pewną kombinatoryczną regułę, mówiącą (w jednej z wersji), że:

Jeżeli n obiektów umieścimy w m < n pudełkach, to znajdzie się pudełko zawierające więcej niż jeden obiekt.

Zaskakujące, prawda? ;-) Wydaje się, że niewiele jest rzeczy bardziej oczywistych. A jednak powyższe twierdzenie doczekało się swojej własnej nazwy – i to nawet takiej, która uwzględnia nazwisko odkrywcy! W języku polskim mówimy mianowicie o zasadzie szufladkowej Dirichleta, a analogią jest podobno układanie skarpetek w szufladach. W angielskim z kolei używa się do tego… gołębi, a reguła jest znana jako pigeonhole principle – w dosłownym tłumaczeniu ‘zasada gołębiej dziury’.

Co jest niezwykłego w tak prostej obserwacji? Otóż jej wyjątkową cechą jest to, że stosuje się do wręcz nieograniczonego spektrum zjawisk różnego typu i wielu dziedzin, pozwalając udowadniać prawdziwość mnóstwa czasami zaskakujących stwierdzeń. Ich ciężar gatunkowy może się wahać od zabawnych, aczkolwiek pouczających, aż do zupełnie kluczowych dla niektórych dziedzin nauki. Oto przykłady:

  • Struktury danych oparte na haszowaniu zawsze muszą uwzględniać metody rozwiązywania kolizji. Ten znany fakt jest konsekwencją tego, iż liczba możliwych kluczy n przekracza (zazwyczaj znacznie) rozmiar pojemnika m, więc nawet przy najlepszej funkcji haszującej znajdą się takie dwa klucze, które zostaną przyporządkowane w to samo miejsce.
  • W pudełku jest 5 czarnych i 5 białych kul. Ile co najmniej kul musimy wybrać, żeby wśród nich znalazła się para tego samego koloru? Nie, wcale nie sześć – wystarczą trzy. Skoro mamy m = 2 kolorów, to już n = 3 kul gwarantuje, że będzie wśród nich para tego samego koloru.
  • Wśród wszystkich obecnie żyjących ludzi co najmniej dwójka wypowiedziała w ciągu swojego dotychczasowego życia identyczną liczbę słów. Nawet gdyby ktoś paplał 24 godziny na dobę z prędkością jednego słowa na sekundę, w ciągu jednej doby nie powie ich więcej niż 86.400. Najstarszy człowiek miał/ma około 130 lat, w związku z czym ilość możliwych wartości dla wielkości ‘liczba wypowiedzianych słów’ to ok. 86.400 * 365,25 * 130, czyli nieco ponad 4 miliardy. Ponieważ na Ziemi żyje obecnie ponad 6 miliardów ludzi – czyli więcej – na mocy zasady szufladkowej wnioskujemy, że musi istnieć co najmniej dwójka, która wypowiedziała w ciągu życia tę samą liczbę słów.
  • Jeśli algorytm kompresji bezstratnej rzeczywiście kompresuje (tj. zmniejsza objętość przynajmniej jednego pliku), to istnieje dla niego taki plik, który po “kompresji” będzie większy niż przed nią. Innymi słowy, nie ma doskonałych metod kompresji i nawet rosyjscy hakerzy nic na to nie poradzą :) Jest to bowiem bezpośrednia konsekwencja zasady ‘gołębiej dziury’.
    Powiedzmy, że najmniejszy plik P faktycznie kompresowany (tj. zmniejszany) przez nas algorytm ma początkowy rozmiar n, zaś po kompresji jest to już k, gdzie k < n. Istnieje skończona liczba plików rozmiaru k, którą oznaczymy N_k. (Jeśli na przykład jest to rozmiar w bajtach, to N = 256^k). Z założenia żaden z tych plików nie zmienia rozmiaru podczas kompresji, więc ich wielkość po skompresowaniu to również k. Oznacza to jednak, że tych N_k plików to wyniki kompresji N_k+1 plików, bo także P (większy niż k) jest kompresowany do jednego z tych plików. Ponieważ N_k + 1 > N_k, na mocy zasady szufladkowej istnieją dwa takie pliki – mianowicie P i jakiś plik rozmiaru k – które są kompresowane do tego samego pliku wyjściowego. Jeśli tak jest, to algorytm nie może być bezstratny – czyli mamy sprzeczność, Q.E.D. :-)

Całkiem sprytne, nieprawdaż? Jak na zupełnie “oczywistą oczywistość”, zasada szufladkowa wykazuje niezwykłą użyteczność w wielu zaskakujących momentach. Warto o niej pamiętać nie tylko podczas poszukiwań pary pasujących skarpetek :)

Tags: ,
Author: Xion, posted under Computer Science & IT, Math »


6 comments for post “Zasada gołębiej dziury”.
  1. gemGreg:
    June 10th, 2010 o 20:09

    ee cos z tymi 5 kulami jednego i 5 innego koluru nie pasuje mi :P Co jak wyciagne 3 kule i beda tego samego koloru?:P nie ma gwarancji ze beda w nich kule roznych kolorow

  2. Dakurels:
    June 10th, 2010 o 20:23

    No sam sobie gemGreg’u odpowiedziałeś. Jak wyciągniesz 3 kule tego samego koloru to przynajmniej dwie z nich będą miały taki sam kolor. Doczytaj jeszcze raz chodzi o kule takiego samego koloru. W przypadku różnego trzeba właśnie 6.

  3. js:
    June 10th, 2010 o 21:39

    Lubie Twoje wpisy blogowe. Luźne podejście do programowania to świetna sprawa. Szczególnie ostatnie stwierdzanie o pasujących skarpetkach ;]

  4. Michał Powaga:
    June 10th, 2010 o 21:55

    Nigdy jaj dotąd o tym nie słyszałem i pewnie dlatego uważałem, że wszystko można ulepszać w nieskończoność ;)

    Ciekawe co by wynikło z tego gdybyśmy nieco “odwrócili” twierdzenie, z założeniem n > m. Podejrzewam jednak, że nie byłoby to wcale ciekawsze ;]

  5. DrVVAL:
    June 11th, 2010 o 2:17

    Popieram, świetne wpisy, ciekawe tematyki, interesujace podejście:)

  6. Liosan:
    June 14th, 2010 o 9:51

    “Jak jest za dużo misiów i za mało łóżeczek, to nie można po Bożemu” ;)

Comments are disabled.
 


© 2017 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.