• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Zasada szufladkowa Dirichleta

    20.01.2011. 10:53
    opublikowane przez: Przemysaw Szydzik

    Niekiedy poważna matematyka zaczyna się od całkiem prostych życiowych obserwacji. Artykuł ma na celu pokazanie jak z pozoru prosta zasada może pomagać rozwiązywać nietypowe i niełatwe matematyczne problemy.
    Wyobraźmy sobie następującą sytuację:

    Mamy piłeczek, które wkładamy do szufladek. Wynika stąd, że w jednej z szufladek będą dwie piłeczki.

    Nie wiemy, w której dokładnie szufladce będą dwie piłeczki. Nie wiemy też, jakie dwie piłeczki się w niej znajdą. Prawdą jest jednak to, że na pewno taka szufladka istnieje. Zmatematyzujmy tę obserwację i zapiszmy ją w formie twierdzenia zwanego Zasadą szufladkową Dirichleta .

    Twierdzenie (Zasada szufladkowa Dirichleta)

    Niech będzie zbiorem takim, że oraz
    Wówczas istnieje takie, że ( oznacza liczbę elementów zbioru ).

    Udowodnimy to twierdzenie korzystając z zasady indukcji matematycznej.

    Dla twierdzenie w naturalny sposób jest spełnione.
    Załóżmy, że twierdzenie jest prawdziwe dla pewnej liczby naturalnej , to znaczy

    (założenie indukcyjne)

    Pokażemy prawdziwość tezy dla . Mamy

    oraz


    Jeśli , czyli , to z założenia indukcyjnego otrzymujemy tezę.
    Jeśli , to i . Spełnione są zatem warunki założenia indukcyjnego i stąd otrzymujemy tezę.
    Jeśli , to i teza jest również prawdziwa.
    Zatem z zasady indukcji matematycznej twierdzenie jest prawdziwe dla każdej liczby naturalnej .

    Zobaczmy teraz jakie konsekwencje niesie za sobą powyższa obserwacja. Pokażemy to na przykładzie kilku zadań, które na pierwszy rzut oka mogą wydawać się trudne bądź nietypowe. Ta prosta zasada pozwala każdemu zrozumieć rozwiązanie dość skomplikowanych problemów.

    Zadanie 1.
    Udowodnij, że wśród mieszkańców Warszawy przynajmniej dwie osoby mają tę samą liczbę włosów na głowie.

    Rozwiązanie.
    Liczba włosów na głowie człowieka nie przekracza 1 000 000. Ponumerujemy szufladki liczbami od 0 do 1 000 000 (jest ich
    1 000 001) i przyporządkujmy każdemu mieszkańcowi szufladkę oznaczoną liczbą jego włosów na głowie. Według źródeł z 2008 roku liczba mieszkańców Warszawy wynosi ok. 1 700 000. Z zasady szufladkowej Dirichleta zastosowanej do naszego przypadku wynika, że przynajmniej dwie osoby są przyporządkowane do jednej szufladki, a co za tym idzie mają tę samą liczbę włosów na głowie.

    Zauważmy, że twierdzenie nie gwarantuje nam istnienia choćby trzech osób z tą samą liczbą włosów na głowie, choć z drugiej strony tego nie wyklucza. Na pewno istnieją dwie, a być może i więcej osób.

    Zadanie 2.
    Wykaż, że w trójkącie równobocznym o boku 4 nie można umieścić 17 punktów tak, by odległość każdych dwóch punktów była większa niż 1.

    Rozwiązanie.
    Podzielmy każdy z boków trójkąta na 4 równe części. Punkty podziału łączymy w taki sposób jak na rysunku poniżej.

    Podział trójkąta równobocznego o boku 4 na 16 trójkątów o boku 1.


    Otrzymaliśmy zatem 16 trójkątów równobocznych o boku 1. Chcąc rozmieścić 17 punktów, musimy w jednym małym trójkącie umiejscowić dokładnie 2 punkty. Korzystając z faktu, że odległość między dwoma punktami leżącymi w trójkącie nie przekracza długości najdłuższego boku, dostajemy uzasadnienie niemożności rozmieszczenia 2 punktów w małym trójkącie tak, by ich odległość była większa niż 1.

    Zadanie 3.
    Danych jest 5 punktów kratowych (czyli o współrzędnych całkowitych) na płaszczyźnie. Wykaż, że środek jednego z odcinków łączących te punkty jest również punktem kratowym.

    Rozwiązanie.
    Układ współrzędnych przesuwamy na płaszczyźnie tak, by wszystkie punkty znajdowały się w I ćwiartce i nadal były punktami kratowymi.
    Współrzędne środka odcinka pomiędzy punktami i wyraża się wzorem:

    Rozróżnijmy cztery szufladki ze względu na obie współrzędne i ich parzystość: , , , ,
    gdzie -współrzędna parzysta, -nieparzysta.

    Wtedy każdy z punktów wpada do jednej szufladki (zakładamy, że 0 jest liczbą parzystą) i w jednej szufladce mamy dwa punkty. Pamiętając, że suma dwóch liczb nieparzystych (a tym bardziej parzystych) jest parzysta, otrzymujemy całkowitoliczbowe współrzędne środka.

    Zadanie 4.
    Udowodnij, że w grupie osobowej są zawsze dwie, które mają w tej grupie tę samą liczbę znajomych. Znajomość określamy następująco: jeśli osoba zna osobę , to osoba zna osobę .

    Rozwiązanie.
    Przez będziemy oznaczać liczbę znajomych osoby w grupie -osobowej. Oczywiście . Zauważmy jednak, że jeśli , to znaczy osoba A nie ma w tej grupie żadnych znajomych, to żadna z osób nie może znać pozostałych osób. To oznacza, że funkcja nie może przyjmować równocześnie wartości i . Stąd wynika, że funkcja przyjmuje różnych wartości. Mamy więc szufladek, którym przyporządkowujemy -osób. Na mocy zasady szufladkowej Dirichleta w jednej szufladce znajdą się 2 osoby, a więc mają one tę samą liczbę znajomych.


    Johann Peter Gustav Dirichlet (1805-1859) matematyk niemiecki pochodzenia francuskiego. Profesor uniwersytetów we Wrocławiu, Berlinie i Getyndze (jako następca Gaussa).


    Literatura:
    Okruchy matematyki, J. Górnicki, PWN.

    Czy wiesz ĹĽe...? (beta)

    W matematyce n-ta liczba trójkątna Tn to liczba obiektów, które – ustawione w regularnej trójkątnej siatce – mogą utworzyć kształt wypełnionego trójkąta równobocznego, w którego boku stoi n obiektów. Początkowymi liczbami trójkątnymi (włączając "zerową" liczbę trójkątną T0 = 0, odpowiadającą "trójkątowi pustemu") są

    Metoda Blocha-Schmigalli, (zwana również jako procedura trójkąta Schmigalli) – metoda optymalnego rozmieszczania punktów zależnych pomiędzy którymi odbywa się przemieszczanie materiału, osób, dokumentów lub informacji. Służy do przestrzennego rozmieszczenia tych punktów w taki sposób aby punkty pomiędzy którymi następuję największa ilość przepływu danego czynnika (materiał, człowiek, informacje) znalazły się jak najbliżej siebie. Punkty te rozmieszczane są na siatce trójkątów dzięki czemu można opracować optymalne rozłożenie dużej ilości takich punktów. Rozmieszczenie tych punktów na siatce trójkątów jest podstawą do dalszego planowania rozmieszczenia przestępnego poszczególnych obiektów. Zastosowanie tej metody pozwala na lepszą organizację pracy, transportu, przepływu materiału, informacji czy osób poprzez skracanie odległości pokonywanych pomiędzy punktami o największej intensywności ruchu.

    Sieć triangulacyjna – zespół punktów geodezyjnych o wyznaczonym położeniu sytuacyjnym i zastabilizowanych w terenie specjalnymi trwałymi znakami geodezyjnymi. Sieci te składają się z zespołu trójkątów połączonych w ten sposób, że mają one wspólne, przyległe boki. Układ tych trójkątów może być różny, np. w postaci łańcucha trójkątów, sieci powierzchniowych. Wierzchołki tych trójkątów są punktami geodezyjnymi (punkty triangulacyjne), których wzajemne położenie zostało wyznaczone przez pomiar co najmniej trzech elementów (dwa kąty i co najmniej jedna długość). Jeżeli jest to łańcuch trójkątów, wystarczy pomierzyć długość jednego boku (tzw. bazę) oraz co najmniej dwa kąty w każdym trójkącie. W praktyce mierzy się w trójkątach wszystkie kąty.

    Sieć triangulacyjna – zespół punktów geodezyjnych o wyznaczonym położeniu sytuacyjnym i zastabilizowanych w terenie specjalnymi trwałymi znakami geodezyjnymi. Sieci te składają się z zespołu trójkątów połączonych w ten sposób, że mają one wspólne, przyległe boki. Układ tych trójkątów może być różny, np. w postaci łańcucha trójkątów, sieci powierzchniowych. Wierzchołki tych trójkątów są punktami geodezyjnymi (punkty triangulacyjne), których wzajemne położenie zostało wyznaczone przez pomiar co najmniej trzech elementów (dwa kąty i co najmniej jedna długość). Jeżeli jest to łańcuch trójkątów, wystarczy pomierzyć długość jednego boku (tzw. bazę) oraz co najmniej dwa kąty w każdym trójkącie. W praktyce mierzy się w trójkątach wszystkie kąty.

    Nierówność trójkąta – twierdzenie matematyczne mówiące, że dla dowolnego trójkąta miara jednego boku musi być mniejsza lub równa sumie miar dwóch pozostałych, ale większa lub równa od różnicy ich miar. W obu przypadkach równości zachodzą dla trójkątów zdegenerowanych, czyli mających postać odcinka: jeden kąt ma wówczas 180°, dwa pozostałe 0°.

    Zasada dualności w geometrii rzutowej mówi, że dowolne prawdziwe twierdzenie na płaszczyźnie rzutowej jest równoważne twierdzeniu które otrzymamy, jeśli zamienimy w nim pojęcia "prosta" na "punkt" i odwrotnie (i odpowiednio "przechodzi przez" na "leży na"). Na przykład, gdy mamy twierdzenie mówiące o współliniowości kilku punktów, istnieje dualne do niego twierdzenie o współpękowości odpowiednich kilku prostych.

    Metoda analizy starożytnych (analisis antiquorum) – metoda rozwiązywania równań. Aby rozwiązać taką metodą równanie f(x) = g(x) zakładamy, że to równanie ma rozwiązanie i że tym rozwiązaniem jest liczba a. Wówczas otrzymujemy zdanie prawdziwe f(a) = g(a). Następnie, stosując prawa arytmetyki, znajdujemy liczbę a. Na koniec sprawdzamy, czy znaleziona liczba jest rozwiązaniem równania.

    Dodano: 20.01.2011. 10:53  


    Najnowsze