Zasada szufladkowa Dirichleta :: Artykuły / Polski Serwis Naukowy

Polecamy również:

Status CUDA Research Center dla Politechniki Gdańskiej

Polskie rozwiązanie telemedyczne ratuje życie na odległość

Rodzinny dawca nerki - optymalne rozwiązanie

Projekt EYESHOTS przynosi rozwiązanie dotykowe

Prof. Gardner: w głowie mamy kilka komputerów, a nie jeden

Eksperci: mamy przełom w leczeniu osób z migotaniem przedsionków

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 $\fs2 n+1$ piłeczek, które wkładamy do $\fs2 n$ 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 $\fs2 X$ będzie zbiorem takim, że $\fs2 |X|>n$ oraz $\fs2 X=X_1\cup X_2\cup\dots\cup X_n.$
Wówczas istnieje $\fs2 i\in\{1,2,\dots,n\}$ takie, że $\fs2 |X_i|\leq 2$ ( $\fs2 |X|$ oznacza liczbę elementów zbioru $\fs2 X$ ).

Udowodnimy to twierdzenie korzystając z zasady indukcji matematycznej.

Dla $\fs2 n=1$ twierdzenie w naturalny sposób jest spełnione.
Załóżmy, że twierdzenie jest prawdziwe dla pewnej liczby naturalnej k>1

, to znaczy

$|X|>k,\, X=X_1\cup\dots\cup X_k\; \Rightarrow \exist_{i\in\{1,\dots,k\}} \;|X_i|\leq 2$ (założenie indukcyjne)

Pokażemy prawdziwość tezy dla $\fs2 k+1$ . Mamy

$X=X_1\cup\dots\cup X_k\cup X_{k+1}\;$ oraz $\;|X|>k+1.$

Jeśli $\fs2 |X_{k+1}|=0$ , czyli $\fs2 X_{k+1}=\emptyset$ , to z założenia indukcyjnego otrzymujemy tezę.
Jeśli $|\fs2 X_{k+1}|=1$ , to $\fs2 Y=X_1\cup\dots\cup X_k$ i $\fs2 |Y|>k$ . Spełnione są zatem warunki założenia indukcyjnego i stąd otrzymujemy tezę.
Jeśli $|\fs2 X_{k+1}|\leq 2$ , to $\fs2 i=k+1$ i teza jest również prawdziwa.
Zatem z zasady indukcji matematycznej twierdzenie jest prawdziwe dla każdej liczby naturalnej $\fs2 n>0$ .

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 $\fs2 (x_1,y_1)$ i (x_2,y_2)

wyraża się wzorem:

$\fs2 $\frac{x_1+x_2}{2},\frac{y_1+y_2}{2}$$

Rozróżnijmy cztery szufladki ze względu na obie współrzędne i ich parzystość: $\fs2 (p,p)$ , $\fs2 (p,n)$ , $\fs2 (n,p)$ , $\fs2 (n,n)$ ,
gdzie $\fs2 p$ -współrzędna parzysta, $\fs2 n$ -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 $\fs2 n>1$ osobowej są zawsze dwie, które mają w tej grupie tę samą liczbę znajomych. Znajomość określamy następująco: jeśli osoba $\fs2 X$ zna osobę $\fs2 Y$ , to osoba $\fs2 Y$ zna osobę $\fs2 X$ .

Rozwiązanie.
Przez $\fs2 f(A)$ będziemy oznaczać liczbę znajomych osoby $\fs2 A$ w grupie $\fs2 n$ -osobowej. Oczywiście $\fs2 0\leq f(A)\leq n-1$ . Zauważmy jednak, że jeśli $\fs2 f(A)=0$ , to znaczy osoba A nie ma w tej grupie żadnych znajomych, to żadna z osób nie może znać pozostałych $\fs2 n-1$ osób. To oznacza, że funkcja $\fs2 f$ nie może przyjmować równocześnie wartości $\fs2 0$ i $\fs2 n-1$ . Stąd wynika, że funkcja $\fs2 f$ przyjmuje $\fs2 n-1$ różnych wartości. Mamy więc $\fs2 n-1$ szufladek, którym przyporządkowujemy $\fs2 n$ -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.

komentuj publikację

Czy wiesz że...?

wersja BETA

Zasada szufladkowa Dirichleta twierdzenie mówiące, że jeżeli

m

przedmiotów włożymy do

n

różnych szufladek, przy czym

m > n

, to co najmniej w jednej szufladce znajdą się co najmniej dwa przedmioty. pełny tekst

Funkcja charakterystyczna zbioru jedno z pojęć matematycznych, mających zastosowanie w teorii miary i teorii ciągów funkcji mierzalnych. Przykładem funkcji charakterystycznej jest funkcja Dirichleta (funkcja charakterystyczna zbioru liczb wymiernych). pełny tekst

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. pełny tekst

Warunki Dirichleta warunki wystarczające aby funkcja okresowa posiadała reprezentację w postaci szeregu Fouriera oraz posiadała transformatę Fouriera. Warunki te były sformułowane przez niemieckiego matematyka Piotra Gustawa Dirichleta. pełny tekst

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. pełny tekst

Moduł "Czy wiesz że...?" (wersja testowa, beta): definicje/pojęcia wygenerowane w obrębie tego modułu pochodzą z Wikipedii i udostępniane są na licencji Creative Commons: uznanie autorstwa, na tych samych warunkach, z możliwością obowiązywania dodatkowych ograniczeń. Dostęp do pełnej wersji każdego hasła (oraz dokładnch informacji na temat licencji, autora oraz edycji) możliwy jest po kliknięciu w odnośnik opisany jako "pełny tekst".