Matematyka.pl

Jeśli mamy rozważać jakieś zadanie z kombinatoryki, to często bardzo przydatna jest pewna zasada. Mówi ona - używając języka potocznego - że gdy pewną ilość przedmiotów umieścimy w szufladach, których jest mniej, to wówczas do którejś z nich trafi więcej niż jeden! Reguła ta - intuicyjnie jasna - ma szereg ciekawych zastosowań i nazywa się czasem zasadą pudełkową (niem. Dirichletsche Schubfachprinzip) , w terminologii angielskiej funkcjonuje ona jako pigeon hole principle, tj. prawo gniazd gołębich. Zasadę można wyrazić bardziej formalnie tak jak poniżej :

\(\displaystyle{ X=X_1 \cup X_2 \cup ..... \cup X_k}\)

to wtedy szufladką jest właśnie każdy zbiór \(\displaystyle{ X_j}\) i któraś z nich zawiera co najmniej dwa elementy, o ile tylko moc zbioru \(\displaystyle{ X}\) jest większa od \(\displaystyle{ k}\).

Inne sformułowanie tej zasady używa pojęcia funkcji. Niech \(\displaystyle{ X, Y}\) będą zbiorami skończonymi, mającymi odpowiednio \(\displaystyle{ n}\) i \(\displaystyle{ k}\) elementów, i mamy \(\displaystyle{ n>k}\). Wtedy żadna funkcja określona na zbiorze \(\displaystyle{ X}\) i o wartościach w zbiorze \(\displaystyle{ Y}\) nie jest różnowartościowa, tj. istnieją różne elementy \(\displaystyle{ a, b \in X}\) w których \(\displaystyle{ f}\) przyjmie tę samą wartość, tj. \(\displaystyle{ f(a)=f(b)}\). Szufladkami są tutaj tzw. warstwy funkcji f, czyli przeciwobrazy jednoelementowych podzbiorów zbioru \(\displaystyle{ Y}\). (przeciwobraz zbioru \(\displaystyle{ Z}\) to zbiór wszystkich elementów \(\displaystyle{ x \in X}\), t. że \(\displaystyle{ f(x) \in Z}\)).

Uogólnienie z-s Dirichleta to fakt: Jeśli \(\displaystyle{ m}\)- krotność liczby szufladek jest mniejsza niż ilość przedmiotów , to wtedy w jednej z nich jest ich \(\displaystyle{ m+1}\) (bądź więcej!)


Słynny problem Paula Erdosa, Dany jest zbiór \(\displaystyle{ A=\{1,2,,...,,2n \}}\)z tego zbioru wybrano- w dowolny sposób liczby \(\displaystyle{ a_1, ....a_n, a_{n+1}}\). Wykazać, że wśród tych liczb istnieją dwie takie, że jedna z nich jest dzielnikiem drugiej.
Rozwiązanie: Tutaj nie od razu widać czym będą nasze szufladki...Każdą liczbę naturalną można zapisać jednoznacznie w postaci \(\displaystyle{ 2^k(2m+1)}\). Uczyńmy tak z każdą z liczb \(\displaystyle{ a_j}\) i określmy funkcję \(\displaystyle{ f(a_j)=m_j}\). Dziedzina funkcji \(\displaystyle{ f}\) to zbiór mocy \(\displaystyle{ n+1}\), zaś może ona przyjąc nie więcej niż \(\displaystyle{ n}\) wartości...Istotnie: \(\displaystyle{ 2n \geq 2^{k_j}(2m_j+1) \geq 2m_j +1}\), tj. \(\displaystyle{ 0 \leq m_j \leq n-1}\). Funkcja \(\displaystyle{ }\)f nie jest więc różnowartościowa, istnieją dwie różne \(\displaystyle{ a_i, a_j}\) t.że. \(\displaystyle{ f(a_j)=f(a_j)=m}\). Są to szukane liczby...ckd.


Niech \(\displaystyle{ A}\) będzie podzbiorem zbioru \(\displaystyle{ \{1,2,3,...,199,200\}}\) złożonym z \(\displaystyle{ 29}\) liczb. Wykazać, że istnieją dwie rozłączne pary elementów zbioru \(\displaystyle{ A}\), mające te same sumy.
Rozwiązanie: Niech ten zbiór: \(\displaystyle{ A= \{a_1, ...a_{29} \},}\) określamy funkcje \(\displaystyle{ f}\), która każdej parze \(\displaystyle{ p=(a,b), a \neq b}\) złożonej z dwóch różnych elementów zbioru \(\displaystyle{ A}\) przyporzadkowuje ich sumę: \(\displaystyle{ f(p)=a+b}\). Skoro wszystkich takich par jest \(\displaystyle{ 406}\) , zaś zbiór wartości funkcji \(\displaystyle{ f}\) to podzbiór \(\displaystyle{ Y=\{3,4, 5, ....., 399 \},}\)tj. zbióru \(\displaystyle{ 397}\)-elementowego, więc - zasady szufladkowej \(\displaystyle{ f}\) musi dla pewnych dwóch różnych par \(\displaystyle{ p, q}\) przyjąć te samą wartość, co więcej żaden element nie może wystąpić w obu parach naraz, i tyle....


Na sali zebrała się pewna liczba osób. Wykazać, że co najmniej dwie z nich mają wśród obecnych tę samą liczbę znajomych...(Uwaga: zakładamy, że jesli osoba A zna osobę B, to także B zna A).
Rozwiązanie: Określmy funkcję: \(\displaystyle{ f(A)}\) jest liczbą osób na sali, jakie zna osoba \(\displaystyle{ A}\). Mamy więc \(\displaystyle{ 0 \leq f(A) \leq k-1}\) (wszystkich osób jest \(\displaystyle{ k}\) ...). Ale nie jest możliwe, aby \(\displaystyle{ f}\) przyjmowała jednocześnie wartość \(\displaystyle{ 0}\) jak i \(\displaystyle{ k-1}\): wtedy istniałaby pewna osoba - nazwijmy ją \(\displaystyle{ X}\) - niemająca znajomych na sali: \(\displaystyle{ f(X)=0}\) i osoba \(\displaystyle{ Y}\), która zna wszystkich: \(\displaystyle{ f(Y)=k-1}\) a więc i osobę \(\displaystyle{ X}\), sprzeczność. Zatem \(\displaystyle{ f}\) przeprowadza \(\displaystyle{ k}\)-elementowy zbiór w zbiór \(\displaystyle{ k-1}\) elementowy, tj. w zbiór \(\displaystyle{ \{0,1, ...k-2 \}}\) lub \(\displaystyle{ \{1,2, ...k-1 \}}\). Zatem nie jest różnowartościowa, tj. mamy pewne dwie osoby \(\displaystyle{ K}\) i \(\displaystyle{ L}\), t.że \(\displaystyle{ f(K)=f(L)}\), czyli mające tę samą liczbę znajomych na sali.


1. Niech \(\displaystyle{ A}\) będzie pewnym zbiorem złożonym z dziesięciu liczb dwucyfrowych. Wykaż, że w tym zbiorze istnieją dwa niepuste podzbiory, być może nierozłączne, t.że sumy elementów obu podzbiorów są równe.
2. Weźmy sobie zbiór \(\displaystyle{ A=\{1, ...n\}}\) i pewien jego podzbiór \(\displaystyle{ k}\)-elementowy , przy czym \(\displaystyle{ 2k>n+1}\). Wykaż, że suma pewnych dwóch liczb tego podzbioru, niekoniecznie różnych, jest równa trzeciej.
3. Niech dana będzie dowolna grupa \(\displaystyle{ G}\) rzędu \(\displaystyle{ n}\), a jej elementy to \(\displaystyle{ a_1, ...., a_n}\). Wówczas istnieją liczby naturalne \(\displaystyle{ i, j}\), t. że \(\displaystyle{ i >j}\) oraz \(\displaystyle{ a_{j+1}\cdot\dots\cdot a_i}\) jest elementem neutralnym grupy.
4. Na płaszczyznie danych jest pięć punktów kratowych, tj punktów o współrzędnych całkowitych. Dowieść, że środek jednego z odcinków łączących te punkty jest również punktem kratowym.
5. Sześć kół leży na płaszczyźnie tak, że środek żadnego z nich nie należy do pozostałych kół. Wykaż, iż koła te nie maja punktu wspólnego.
6. Udowodnić, że każdy ciąg, który składa się z \(\displaystyle{ mn+1}\) różnych liczb rzeczywistych, musi zawierać podciąg rosnący długości co najmniej \(\displaystyle{ m+1}\) lub podciąg malejący długości co najmniej \(\displaystyle{ n+1}\).
7. Na sferze obrano \(\displaystyle{ 13}\) punktów Dowieść, że wśrod nich istnieją dwa takie, których odległość jest mniejsza niż \(\displaystyle{ 2\sqrt{3}}\) promienia sfery.
wsk. W sferę wpisujemy dwunastościan foremny. I z każdego spośród tych punktów prowadzimy odcinek łączacy go ze środkiem sfery.
8. Na nieskończonej szachownicy stoi \(\displaystyle{ 2n-1}\) koników szachowych. Czy można wybrać spośród nich \(\displaystyle{ n}\) takich, iż żadne dwa spośród nich się nie atakują?
9. Na płaszczyźnie narysowano \(\displaystyle{ 2n+1}\) okręgów o promieniu \(\displaystyle{ \sqrt{5}}\) i o środkach w punktach kratowych. Wykaż, że można zetrzeć \(\displaystyle{ n}\) spośród tych okręgów tak, by wśród pozostałych żaden nie przechodził przez środek innego.
10. Nauczyciel na każdej z najbliższych \(\displaystyle{ 14}\) lekcji postanowił przepytać co najmniej jedną osobę, tak by łącznie przepytać nie więcej niż \(\displaystyle{ 20}\) osób. Wykaż, że niezależnie od sposobu rozdzielenia pytanych uczniów istnieje kilka kolejnych lekcji, na których przepytanych zostanie dokładnie \(\displaystyle{ 7}\) osób.
11. Udowodnij, że spośród dowolnych \(\displaystyle{ n+2}\), liczb naturalnych, gdzie \(\displaystyle{ n>0}\), można wybrać takie dwie \(\displaystyle{ a, b}\), że liczba \(\displaystyle{ a^2 - b^2}\) jest podzielna przez \(\displaystyle{ 2n}\).
12. W okrąg o obwodzie \(\displaystyle{ 24}\) wpisano trójkąt równoboczny oraz kwadrat, które nie mają wspólnych wierzchołków. Wykazać, że co najmniej jeden z \(\displaystyle{ 7}\) łuków, na które wierzchołki podzieliły okrąg ma długość nie większą niż \(\displaystyle{ 1}\).

13. *(zadanie V. Linisa- trudne), Dane jest koło \(\displaystyle{ K}\) o promieniu \(\displaystyle{ 16}\) i mamy też pierścień kołowy \(\displaystyle{ P}\) o promieniach: wewnętrznym \(\displaystyle{ r=2}\) i zewnętrznym \(\displaystyle{ R=3}\), Wewnątrz \(\displaystyle{ K}\) wybrano dowolnie \(\displaystyle{ 650}\) punktów. Wykaż, że da się tak ustawić \(\displaystyle{ P}\), aby przykrył przynajmniej \(\displaystyle{ 10}\) z tych punktów.