Zasada Szufladkowa Dirichleta zadania i teoria – Indeks w Kieszeni

Zasada Szufladkowa Dirichleta (często nazywana też twierdzeniem Dirichleta) to jedno z najprostszych, a zarazem najczęściej wykorzystywanych twierdzeń w matematyce. Mówi ono, że: Jeśli próbujemy rozmieścić więcej obiektów niż mamy szufladek, to w co najmniej jednej szufladce znajdą się co najmniej dwa obiekty. Innymi słowy, jeśli mamy 8 osób i 7 dni tygodnia, zawsze znajdzie się przynajmniej dwójka ludzi urodzona tego samego dnia. Proste, prawda? A jednak to stwierdzenie ma ogromne zastosowanie w matematyce olimpijskiej i konkursowej.

Najważniejsze informacje o zasadzie szufladkowej Dirichleta, których dowiesz się z tego artykułu:

1. Jeśli mamy więcej elementów niż „szufladek”, to przynajmniej dwie rzeczy muszą trafić do tego samego miejsca. To intuicyjna, a jednocześnie niezwykle ważna zasada.
2. To prosta konsekwencja arytmetyki – jeśli „dzielimy” więcej elementów niż miejsc, musimy coś powtórzyć.
3. Choć brzmi jak banał, jest jednym z fundamentów myślenia matematycznego. To narzędzie, które „zmusza” do zauważenia ukrytych powtórzeń i zależności.

Twierdzenie Dirichleta występuje na Olimpiadzie Matematycznej, Przygotowując się do tego konkursu, zwróć uwagę również na temat jednokładności.

---

Zasada Szufladkowa Dirichleta na Olimpiadzie Matematycznej

---

Bardziej doświadczeni Olimpijczycy z pewnością znają Zasadę Szufladkową Dirichleta (i mogą śmiało przejść kilka akapitów do przodu). Dla tych, którzy swoją przygodę z Olimpiadą dopiero zaczynają, nakreślę szybko jej treść. Jest to po prostu stwierdzenie mówiące, że jeśli pewną liczbę obiektów próbujemy umieścić w mniejszej od niej liczbie szufladek, to w pewnej szufladce muszą znaleźć się przynajmniej dwa obiekty. Oczywiście w miejsce słów „obiekty”, „szufladki” oraz „umieścić” możemy wstawić dowolne inne określenia nadające powyższemu zdaniu sens. 

Naszymi obiektami może być chociażby osiem osób, a szufladkami dni tygodnia, w których będziemy umieszczać te osoby. Podzielimy je przykładowo na podstawie tego, którego dnia się urodziły, to otrzymamy wówczas stwierdzenie, że wśród dowolnej grupy ośmiu osób znajdziemy dwie urodzone tego samego dnia tygodnia.

---

---

Źródło: pixabay.com

---

Zasada Szufladkowa Dirichleta jako schemat myślowy

---

Wymienione przed chwilą stwierdzenie (jak i cała zasada) nie brzmią zbyt skomplikowanie. Ich dowód nie jest bowiem zbyt zawiły i można określić go jako dość intuicyjny (z formalnego punktu widzenia przeprowadza się go najczęściej nie wprost – zachęcam do jego przeprowadzenia w ramach ćwiczeń).

Zasada Szufladkowa Dirichleta (ZSD) doczekała się swojej własnej nazwy głównie dlatego, że jest „schematem myślowym”, do którego łatwo możemy się odwołać w trakcie rozwiązywania zadania. Jest to po prostu konstrukcja ułatwiająca nam przeprowadzenie i napisanie rozumowania, a także sprawdzenie jego poprawności – czyni rozwiązanie bardziej przejrzystym. Nie jest to jednak nigdy samodzielna technika rozwiązywania zadań i zawsze idzie w parze z jakimś dodatkowym rozumowaniem, a w zasadzie to ona sama jest często jedynie dodatkiem.

---

---

Źródło: pixabay.com

---

Zasada Szufladkowa Dirichleta zadania

---

Zadanie I

---

Każdy punkt płaszczyzny pomalowano na jeden z dwóch kolorów. Udowodnij, że istnieją dwa punkty odległe o 1, które są tego samego koloru.

Dowód

---

Spójrzmy na trójkąt równoboczny o boku 1. Obiektami niech będą jego wierzchołki (3), a szufladkami kolory (2). Na mocy Zasady Szufladkowej Dirichleta otrzymujemy, że pewne dwa obiekty będą w tej samej szufladce, co tłumaczy się jako: pewne dwa wierzchołki będą tego samego koloru. A skoro są odległe o 1 (jak to w trójkącie równobocznym o boku 1 bywa), to nasze zadanie jest zakończone.

Jak widzimy, w treści zadania nie ma nic, co mogłoby w oczywisty sposób sugerować skorzystanie z Zasady Szufladkowej Dirichleta. Patrząc na zadanie i ogrom możliwości (mamy w końcu płaszczyznę pokolorowaną w dowolny sposób dwoma kolorami; trudno jest sobie nawet wyobrazić, jak miałoby to wyglądać), dochodzimy do wniosku, że należy się skupić jedynie na małym podzbiorze punktów płaszczyzny i próbować na nim przeprowadzić jakieś rozumowanie. 

W ten sposób możemy trafić na rozwiązanie zbliżone do powyższego. Użycie Zasady nasuwa się samo – można byłoby o niej nie wspominać, ale jej użycie nadaje rozwiązaniu intuicyjnego sensu. Spróbujmy czegoś trudniejszego:

---

Zadanie II

---

Wykaż, że istnieje liczba Fibonacciego kończąca się dziesięcioma zerami (liczby Fibonacciego to elementy ciągu F_n zadanego poprzez warunki F_0=0, F_1=1 oraz F_(n+2)=F_(n+1)+F_n dla każdego n≥0).

Dowód

---

Liczba kończy się dziesięcioma zerami wtedy i tylko wtedy, gdy jest niezerowa i podzielna przez 10^10. Będziemy więc rozpatrywać jedynie reszty z dzielenia wyrazów ciągu Fibonacciego przez tę właśnie liczbę. Znając reszty dowolnych dwóch sąsiednich wyrazów jesteśmy w stanie wyznaczyć reszty wszystkich następnych (jak i poprzednich – będzie to istotne później), stąd jeśli w pewnym momencie dowolna para reszt powtórzy się, to cały ciąg reszt się zapętli. To jednak musi nastąpić, ponieważ ciąg ma nieskończenie wiele wyrazów, a jest tylko skończenie wiele par reszt z dzielenia przez 10^10 (dokładniej jest ich 10^20). 

Tak jak wspomnieliśmy wcześniej, patrząc wstecz do reszt poprzednich wyrazów dochodzimy do wniosku, że każda taka „pętla” musi zawierać tę samą resztę z dzielenia przez 10^10, F_0=0. Dowodzi to, że istnieje nawet nieskończenie wiele takich wyrazów.

Można zadać pytanie, w którym momencie skorzystaliśmy z Zasady Szufladkowej Dirichleta, nie wspominamy o niej przecież ani razu. Odwołujemy się do niej pośrednio w zdaniu „To jednak musi nastąpić, ponieważ ciąg ma nieskończenie wiele wyrazów, a jest tylko skończenie wiele par reszt z dzielenia przez 10^10” – stosujemy tu tzw. „nieskończoną Zasadę Szufladkową Dirichleta”, gdzie mamy nieskończenie wiele obiektów, a jedynie skończenie wiele szufladek. Widzimy więc, że nie zawsze musimy się do Zasady odwoływać w sposób dosłowny, niemniej jednak wciąż dobrze jest mieć z tyłu głowy, że z niej korzystamy. 

Dla ciekawych dodam jedynie, że długość takiej „pętli” nazywa się okresem Pisano (Leonardo Pisano to właśnie Fibonacci). Gdy liczba, której reszty z dzielenia rozpatrujemy jest równa 10^10 okres ten ma długość 1.5∙10^10 (można to sprawdzić patrząc na ciąg A096363 w OEIS). Popatrzmy teraz na zadanie, w którym użycie Zasady Szufladkowej Dirichleta jest oczywiste, jednak na pierwszy rzut oka nie wiadomo, do czego ją zastosować

---

Zadanie III

---

Wykaż, że wśród dowolnych siedmiu liczb rzeczywistych istnieją takie dwie, że:

---

---

Dowód

---

Zadanie można de facto rozwiązać tylko w jeden sposób. Aby wpaść na to rozwiązanie trzeba być dobrze zaznajomionym z trygonometrią. Należy bowiem w powyższym wyrażeniu dostrzec wzór na tangens różnicy. Korzystając z faktu, że tangens (ograniczony do przedziału  [-π/2,π/2]) jest suriekcją (tj. przyjmuje wszystkie wartości rzeczywiste) możemy każdej tych siedmiu liczb przyporządkować jedną z powyższego przedziału, tak by jej tangens był jej równy. Wówczas wśród tej siódemki nowych liczb mamy znaleźć taką dwójkę, która spełnia nierówność:

---

---

A to już proste zastosowanie Zasady Szufladkowej Dirichleta.

---

Gdzie jeszcze można spotkać i wykorzystać Zasadę Szufladkową Dirichleta?

---

Zadań, w których Zasada Szufladkowa Dirichleta znajduje zastosowanie jest naprawdę wiele. Wśród nich można jednak wyodrębnić dwie całkiem spore grupy.

• Pierwszą z nich są zadania związane z liczbami niewymiernymi – najbardziej klasycznym jest wykazanie, że dla każdej liczby rzeczywistej x z przedziału [0,1] i dowolnej liczby niewymiernej α, i dowolnie małej liczby rzeczywistej ε>0, istnieje takie naturalne n, że część ułamkowa liczby nα jest odległa od x o nie więcej niż ε (można pokazać nawet więcej – ciąg części ułamkowych liczb nα jest równomiernie rozłożony na przedziale [0,1], nie jest to jednak proste do udowodnienia biorąc pod uwagę, że trudno nawet zdefiniować, co „równomiernie rozłożony” oznacza).
• Drugą grupą są różnego rodzaju zadania geometryczne – wykazywanie, że w pewnej grupie punktów wewnątrz jakiegoś obiektu znajdują się dwa oddalone o nie więcej niż pewna wartość. Tutaj wyzwaniem jest odpowiednie dobranie szufladek, tzn podzielenie zadanego obszaru na mniejszą liczbę części niż jest punktów w zadaniu tak, by w każdym obszarze dowolne dwa punkty były dostatecznie blisko siebie.

---

---

Źródło: pixabay.com

---

Zadania Zasady Szufladkowej Dirichleta dla ambitnych

---

Na koniec zostawiam Cię z kilkoma zadaniami do samodzielnego rozwiązania. Ich poziom trudności sięga od stosunkowo prostych do dość trudnych – powodzenia!

---

Zadanie IV

---

Ile osób potrzeba, by mieć pewność, że pewne trzy urodziły się tego samego dnia tygodnia i tego samego miesiąca?

---

Zadanie V

---

Liczby pierwsze p, q, r są większe od 3. Pokaż, że 48|(a − b)(b − c)(c − a).

---

Zadanie VI

---

Ze zbioru {1,2,…,100} wybieramy 51 liczb. Wykaż, że pewne dwie są względnie pierwsze (tj. nie mają wspólnego dzielnika pierwszego).

---

Zadanie VII

---

Ze zbioru {1,2,…,100} wybieramy 51 liczb. Wykaż, że jedna z nich jest podzielna przez drugą.

---

Zadanie VIII

---

Wykaż, że wśród dowolnych sześciu punktów w prostokącie 3×4 pewne dwa są odległe o nie więcej niż √5.

---

Najważniejsze zastosowania zasady szufladkowej Dirichleta

---

• Kombinatoryka – udowadnianie istnienia pewnych konfiguracji.
• Teoria liczb – dowody związane z resztami z dzielenia, liczbami pierwszymi czy ciągami.
• Geometria – wykazywanie, że punkty muszą być „wystarczająco blisko siebie”.

---

Zasada szufladkowa Dirichleta – najważniejsze informacje

---

Zasada szufladkowa Dirichleta to jedno z najprostszych, a jednocześnie najpotężniejszych narzędzi matematycznych. Jej intuicyjne sformułowanie – jeśli obiektów jest więcej niż miejsc, to co najmniej dwa muszą trafić do tego samego miejsca – ma ogromne znaczenie w kombinatoryce, geometrii i teorii liczb. To właśnie dzięki niej można udowadniać istnienie pewnych konfiguracji, zależności i własności, które na pierwszy rzut oka wcale nie są oczywiste.

Choć twierdzenie brzmi banalnie, jego zastosowania pokazują, że matematyka często kryje niezwykłą moc w prostych ideach. Dlatego Zasada Szufladkowa Dirichleta pojawia się nie tylko w zadaniach olimpijskich i konkursowych, ale także w praktycznych rozumowaniach matematycznych. To fundament, którego warto się nauczyć i dobrze rozumieć – bo otwiera drogę do wielu trudniejszych zagadnień.

Chcesz kompleksowo przygotować się do Olimpiady Matematycznej? Sprawdź naszą ofertę i zapisz się na kursy Indeksu w Kieszeni!

---

---

FAQ – najczęściej zadawane pytania

---

---

Czym jest zasada szufladkowa Dirichleta?

---

To twierdzenie mówiące, że jeśli liczba obiektów jest większa niż liczba miejsc, to co najmniej dwa obiekty znajdą się w tym samym miejscu.

---

Czy zasada szufladkowa Dirichleta ma zastosowania praktyczne?

---

Tak – od prostych problemów z urodzinami, przez kombinatorykę, aż po dowody w teorii liczb i geometrii.

---

Dlaczego nazywa się to twierdzeniem Dirichleta?

---

Twierdzenie nazwane zostało na cześć niemieckiego matematyka Johanna Dirichleta, który spopularyzował tę zasadę w XIX wieku.

---

Czy zadania z zasadą szufladkową Dirichleta pojawiają się na Olimpiadzie Matematycznej?

---

Tak – to jedno z klasycznych narzędzi stosowanych w zadaniach olimpijskich i konkursowych.