Dołącz do czytelników
Brak wyników

Matematyka w praktyce

18 marca 2021

NR 48 (Marzec 2021)

Zasada Szufladkowa Dirichleta, czyli proste narzędzie do (również) niebanalnych problemów

93

W artykule zostały zebrane zadania o zróżnicowanym poziomie trudności, wykorzystujące Zasadę Szufladkową Dirichleta. Do niemal każdego zadania dołączone jest rozwiązanie bądź szkic rozwiązania. Temat może być przedstawiony podczas zajęć dodatkowych/ /kółek zainteresowań. W niektórych zadaniach wykorzystuje się niebanalne pomysły, warto pokazać je uczniom przygotowującym się do konkursów matematycznych.

Gdy n + 1 przedmiotów włożymy do n szufladek, na pewno w którejś szufladce znajdą się przynajmniej dwa przedmioty – to potoczne brzmienie twierdzenia zwanego Zasadą Szufladkową Dirichleta. Ogólniejsze wersje również są łatwe do odkrycia:

POLECAMY

  • A gdy włożymy n · k + 1 przedmiotów do n szufladek, to ile co najmniej znajduje się ich w którejś szufladce?1
  • Ile musimy mieć przedmiotów, aby mieć pewność, że wkładając je do n szufladek, w którejś znajdzie się co najmniej m przedmiotów?2
  • A gdy włożymy n przedmiotów do k szufladek, ile (co najmniej) na pewno znajdzie się w jednej z nich?

Odpowiedź na ostatnie z ww. pytań może wymagać już dokonania kilku prób na konkretnych liczbach, a forma odpowiedzi może zależeć od tego, z czym nasi uczniowie już się zetknęli. Jeśli poznali część całkowitą liczby x (zwaną też cechą lub podłogą i oznaczaną [x] bądź ⎣x⎦) oraz sufit (⎡x⎤), możemy spodziewać się odpowiedzi w najbardziej zwartej formie: ⎡⎤. Jeśli nie, odpowiedź pewnie będzie bardziej opisowa: 
Jeśli n dzieli się przez k, to w którejś szufladce znajduje się na pewno co najmniej  przedmiotów, a jeśli n nie dzieli się przez k, to w którejś szufladce znajduje się co najmniej część całkowita3 liczby , powiększona o 1.
Wiele zadań o różnym stopniu trudności wykorzystuje Zasadę Szufladkową Dirichleta. Zarówno dla starszych klas szkoły podstawowej, jak i dla uczniów szkół ponadgimnazjalnych/ponadpodstawowych można znaleźć ciekawe problemy. Młodsi uczniowie mogą rozpocząć przygodę z ZSD od zadań typu:

  • uzasadnij, że pewnych dwóch mieszkańców Warszawy ma tyle samo włosów na głowie4,
  • uzasadnij, że pewnych dwóch/trzech5 uczniów klasy ma urodziny w tym samym miesiącu.

Dla starszych rozpocznę od zadania z drugiego etapu 69. Olimpiady Matematycznej, które można było rozwiązać, korzystając z ZSD i… cierpliwości6.

Zadanie 1 
Dane są takie pięcioelementowe podzbiory {A1, A2, … , Ak} zbioru {1, 2, … , 23}, że dla wszystkich 1 ≤ i ≤ j ≤ k zbiór  Ai ∩ Aj ma co najwyżej trzy elementy. Wykazać, że k ≤ 2018.
Rozwiązanie: Przypuśćmy, że k > 2018. Wypisujemy po kolei wszystkie liczby ze wszystkich zbiorów A1, A2, … , Ak, czyli 5k liczb. Ponieważ k > 2018 wypisaliśmy przynajmniej 2019 · 5 = 10 095 liczb ze zbioru {1, 2, … , 23}, więc któraś z nich – nazwijmy ją a – powtórzyła się przynajmniej ⎡⎤ = ⎡438,91…⎤ = 439 razy – po raz pierwszy wykorzystaliśmy ZSD. Niech B1, B2, … , B439 będą tymi zbiorami z {A1, A2, … , Ak}, które ją zawierają. I znowu wypisujemy z nich wszystkie elementy, powtarzając, ale już bez a, które występowało w każdym z nich. Wypisaliśmy 4 · 439 liczb ze zbioru 22-elementowego (tj. ze zbioru {1, 2, 3, … , 23} \ {a}), więc któraś, nazwijmy ją b, powtórzyła się przynajmniej 80 razy7. Niech C1, C2, … , C80 będą tymi zbiorami z {B1, B2, … , B439}, które zawierają b. Cierpliwie powtarzamy procedurę: wypisujemy z nich wszystkie elementy z powtórzeniami, ale już bez a i bez b, które należą do każdego z nich. Wypisaliśmy 3 · 80 liczb ze zbioru 21-elementowego, więc któraś, nazwijmy ją c, powtórzyła się 12 razy8. Niech D1, D2, … , D12 będą tymi zbiorami spośród {C1, C2, … , C80}, które ją zawierają. 
I jeszcze raz: wypiszmy elementy tych zbiorów (oczywiście, znowu z powtórzeniami) bez a, b, c. Wypisaliśmy 2 · 12 elementów ze zbioru 20-elementowego, czyli któraś liczba, powiedzmy d, powtórzyła się 2 razy9. 
Powiedzmy, że była w zbiorze  Di i Dj dla pewnych 1 ≤ i ≤ j ≤ 12. Ale to oznacza, że Di ∩ Dj ma przynajmniej 4 elementy wspólne: a, b, c, i d – sprzeczność z założeniem, że dla wszystkich 1 ≤ i ≤ j ≤ k zbiór Ai ∩ Aj ma co najwyżej trzy elementy. Do tej sprzeczności doprowadziło przypuszczenie k > 2018. Pokazaliśmy zatem, że k ≤ 2018. 

Gdy już przekonaliśmy się, że znajomość ZSD może pomóc na poważnym konkursie, jakim jest Olimpiada Matematyczna, wróćmy do nieco bardziej oczywistych zadań. Najpierw te o resztach z dzielenia. Uczniowie powinni wiedzieć, że różnica dwóch liczb dzieli się przez n wtedy i tylko wtedy, gdy obie te liczby mają tę samą resztę z dzielenia przez n; możliwe reszty z dzielenia przez n to 0, 1, 2, … , n − 1 jest ich więc n.

Zadanie 2 
Danych jest 11 liczb całkowitych. Wykazać, że można wśród nich znaleźć takie dwie, że ich różnica jest podzielna przez 10.
Uwaga. Można tezę sformułować też następująco: Wykazać, że można wśród nich znaleźć dwie o tych samych cyfrach jedności.

Zadanie 3 
Danych jest 7 liczb całkowitych. Wykazać, że można wśród nich znaleźć takie dwie, że różnica ich kwadratów jest podzielna przez 10.
Wskazówka: Ile jest możliwych reszt z dzielenia przez dziesięć kwadratów liczb całkowitych? Tylko sześć: to 0, 1, 4, 9, 6, 5. Spośród tych siedmiu danych liczb znajdę więc takie dwie, że ich kwadraty mają taką samą resztę z dzielenia przez 10.

Można też pytać o minimalną liczbę „przedmiotów”.

Zadanie 4 
Znaleźć najmniejszą liczbę naturalną k o tej własności, że wśród dowolnych k różnych liczb całkowitych można wskazać dwie, których różnica sześcianów jest podzielna przez 9. 
Wskazówka: Ile jest możliwych reszt z dzielenia przez 9 sześcianów liczb całkowitych? Tylko trzy: to 0, 1, 8. Jak będziemy mieć cztery liczby, to z ZSD znajdziemy wśród nich (przynajmniej) dwie o pożądanej w zadaniu własności. Trzy to za mało: liczby 0, 1, 2 mają różne reszty z dzielenia swoich sześcianów przez 9, zatem k = 4.

Kolejne zadanie też jest o podzielności, a przy okazji powtarzamy, jak znaleźć środek odcinka.

Zadanie 5 
Na kartce w kratkę zaznaczono 5 punktów kratowych. Udowodnić, że środek odcinka łączącego pewne dwa spośród nich jest także punktem kratowym.
Wskazówka: Wprowadzić układ współrzędnych, rozważyć parzystość współrzędnych punktów kratowych. Zauważyć, że środek odcinka jest punktem kratowym, gdy pierwsze współrzędne końców tego odcinka  są tej samej parzystości oraz drugie są tej samej parzystości. Mamy cztery możliwe typy punktów kratowych: o obu współrzędnych parzystych, obu nieparzystych, pierwszej parzystej i drugiej nieparzystej oraz pierwszej nieparzystej, a drugiej parzystej. A skoro punktów jest 5, to dwa z nich są tego samego typu.

W kolejnym zadaniu liczbę 2021 można zastąpić jakąkolwiek inną.

Zadanie 6 
Wykazać (bez użycia kalkulatora/komputera), że w ciągu Fibonacciego (F1 = F2 = 1, Fn + 2 = Fn + 1 + Fn) można znaleźć liczbę podzielną przez 2021.
Wskazówka: Niech rn będzie resztą z dzielenia liczby Fn przez 2021. Rozważmy pary (rn, rn + 1). 
Czy znajdę dwie takie same pary? Jasne, że tak, bo tych par jest przecież nieskończenie wiele, a możliwych różnych par jest 2021 · 2021. Mamy więc (rn, rn + 1)
= (rm, rm + 1) dla pewnych różnych n, m naturalnych.
Dla ustalenia uwagi niech m > n. Zauważmy, że z równości rn = rm i rn + 1 = rm + 110 wynika, iż rn − 1 = rm − 1, stąd z kolei otrzymujemy rn − 2 = rm − 2 i tak dalej…, aż dojdziemy do r2 = rm − n + 2  i  r1 = rm − n + 1.  Ale r2 = r1 = 1, czyli  rm − n + 2 = rm − n + 1. Ile wynosi zatem rm − n? Zero. Czyli Fm − n to szukana liczba.

Suma liczb a podzielność wymaga trochę więcej pomysłowości niż różnica, o czym świadczą kolejne zadania.

Zadanie 7 
Danych jest k (k − 1) + 1 różnych liczb całkowitych. Udowodnić, że można spośród nich wybrać k liczb, których suma jest podzielna przez k.
Wskazówka: Z ZSD pewne k liczb ma tę samą resztę z dzielenia przez k, ich suma daje liczbę podzielną przez k.

Zadanie 8 
Niech k będzie nieparzystą liczbą naturalną. Danych jest (k − 1)(k − 1) + 1 różnych liczb całkowitych. Udowodnić, że można spośród nich wybrać k liczb, których suma jest podzielna przez k.
Wskazówka: Tym razem mamy tylko (k − 1)(k − 1) + 1 liczb, trzeba więc nieco bardziej się wysilić. Albo spośród tych liczb można znaleźć k o k różnych resztach z dzielenia przez k, wtedy ich suma da liczbę o reszcie 0 + 1 + 2 + … + (k − 1), czyli 0 z dzielenia przez k.
Albo nie, i wtedy te (k − 1)(k − 1) + 1 liczb daje co najwyżej k − 1 możliwych reszt z dzielenia przez k (i (k − 1) (k − 1) + 1 liczb (i to już nie jest za mało, aby skorzystać z ZSD). k o tej samej reszcie znajdziemy i tak jak w poprzednim zadaniu wystarczy je wybrać, bo ich suma będzie się dzieliła przez k.

W ostatnim zadaniu pomogło rozważenie przypadków, tak jest także w następnym.

Zadanie 9 
Danych jest 2021 liczb całkowitych. Wykazać, że zawsze można wśród nich znaleźć takie trzy różne liczby a, b, c, że a · (b − c) jest podzielne przez 2021.
Wskazówka: Albo któraś z tych 2021 liczb dzieli się przez 2021 (i to będzie szukane a), albo któreś dwie mają te same reszty z dzielenia przez 2021, bo wtedy możliwych reszt jest 2020, a liczb 2021, i to będą szukane b i c.

Zauważenie, że „szufladek” jest tak naprawdę mniej niż przedmiotów (choć pozornie jest ich tyle samo), jest kluczem do rozwiązania dwóch kolejnych zadań, a może warto zauważyć z uczniami, że to są tak naprawdę takie same zadania…

Zadanie 10 
W turnieju piłkarskim, w którym docelowo każda drużyna ma zagrać z każdą inną, bierze udział n zespołów. Uzasadnić, że w dowolnym momencie trwania turnieju znajdą się dwie drużyny, które rozegrały do tego momentu tę samą liczbę meczów.
Wskazówka: Rozważmy dowolny moment turnieju. Każda drużyna rozegrała od 0 do n − 1 meczów. Prawda. Mamy więc n przedmiotów (drużyn) i n szufladek (liczba rozegranych meczy). Czy można trochę to „poprawić”? Jeśli któraś drużyna rozegrała zero meczów, to ani jedna nie mogła rozegrać n − 1; jeśli któraś rozegrała n − 1, to ani jedna zero. Więc szufladek tak naprawdę jest n − 1: albo {0, 1, 2, … , n − 2}, albo {1, 2, 3, … , n − 1}. 

W obydwu sytuacjach znajdziemy dwie drużyny, które rozegrały tę samą liczbę meczów.

Zadanie 11 
Pokazać, że w dowolnej grupie ludzi są dwie osoby, które mają w tej grupie jednakowe liczby znajomych.

Zadanie 12 można potraktować jako wskazówkę do zadania 13.

Zadanie 12 
W tabeli o 65 wierszach i 5 kolumnach pola pomalowane są na biało albo czarno. Wykaż, że znajdziemy trzy wiersze i trzy kolumny tak, aby pola z ich przecięć miały ten sam kolor.
Wskazówka: Ile jest różnych pokolorowań wiersza? 25 = 32.

Ile wierszy na pewno będzie identycznych? 
Z ZSD: \({65\over32 }\)  =  3. Z tych wierszy trzeba wybierać dalej. Są tam trzy pola białe albo trzy pola czarne (jeszcze raz powołujemy się na ZSD). 
Wybieram kolumny z tymi trzema polami i te trzy identyczne wiersze.

Zadanie 13 
Pomalujmy płaszczyznę w dowolny sposób na dwa kolory: biały i czarny (to znaczy przypiszmy każdemu punktowi płaszczyzny jeden z tych dwu kolorów). Pokazać, że na takiej płaszczyźnie istnieje prostokąt, który ma wszystkie wierzchołki tego samego koloru.
Wskazówka: O pewnych punktach płaszczyzny można myśleć jako o polach tabeli jak z poprzedniego zadania. Wystarczy więc rozważyć „tabelę” o właściwych wymiarach (Jakich? 9 na 3) i rozwiązać jak poprzednie zadanie…

Też o kolorowaniu płaszczyzny, ale wydaje się, że znacznie łatwiejsze od poprzedniego, jest kolejne zadanie.

Zadanie 14 
Pomalujmy płaszczyznę w dowolny sposób na dwa kolory: biały i czarny (to znaczy przypiszmy każdemu punktowi płaszczyzny jeden z tych dwu kolorów). 
Pokazać, że na takiej płaszczyźnie istnieją dwa punkty jednakowego koloru, odległe od siebie o 2021.
Wskazówka: Rozważmy trzy wierzchołki trójkąta równobocznego o boku  i… dalej wszystko jasne.

Rozwiązania trzech kolejnych zadań zawierają ciekawy pomysł: choć mamy do dyspozycji dużo „przedmiotów”, przyglądamy się tylko części z nich, nie potrzebujemy wszystkich.

Zadanie 15 
Wykazać, że z dowolnego zbioru 2021 liczb całkowitych można wybrać taki podzbiór, że suma liczb z tego podzbioru dzieli się przez 2021. 
Wskazówka: Rozważmy tylko takie podzbiory:  {x1}, {x1, x2}, … , {x1, x2, … , x2021} danego zbioru . Jeśli któraś suma x1 + x2 + … xk jest podzielna przez 2021, to zadanie skończone, a jeśli nie, to znajdą się dwa zbiory o sumach liczb, które dają tę samą resztę 
z dzielenia przez 2021, powiedzmy są to {x1, x2, … , xk} i {x1, x2, … , xl}, dla ustalenia uwagi k > l. Co można powiedzieć o sumie liczb ze zbioru {xl + 1, … , xk}?

Zadanie 16 
W ciągu jednego miesiąca (30 dni) pewne dziecko zjadło n < 50 cukierków, przy czym codziennie jadło całkowitą i dodatnią liczbę cukierków. Udowodnić, że w pewnym okresie kolejnych dni zjadło dokładnie 10 cukierków.
Wskazówka: Podzielmy rozważany miesiąc na trzy grupy: dni od 1 do 10, od 11 do 20 i od 21 do 30. 
W każdej z tych grup dowodzimy jak w Zadaniu 15, że istnieją takie kolejne dni, że suma liczb cukierków zjedzonych w tych dniach dzieli się przez 10. Czyli albo w którejś grupie jest równa 10, albo 
w każdej z tych trzech grup wynosi przynajmniej 20 – ale to niemożliwe, bo n < 50.

Zadanie 17 
Udowodnić (bez kalkulatora), że pewna wielokrotność liczby 2021 ma w zapisie dziesiętnym same jedynki. 
Wskazówka: Rozważmy liczby: 1, 11, 111, 1111, …
Dwie spośród nich mają tę samą resztę z dzielenia przez 2021, ich różnica, która jest liczbą postaci 11111 … 10000 … 0 = 11 … 1 · 10k, dzieli się przez 2021. Ale 10k jest względnie pierwsze z 2021. Stąd wynika teza.

Czas na zadania o podobnej treści, ale różnym stopniu trudności. Pierwsze łatwe, drugie średnie (warto sobie uświadomić, że dwie kolejne liczby naturalne są zawsze względnie pierwsze), trzecie niebanalne!

Zadanie 18 
Niech dla ustalonego n naturalnego A będzie podzbiorem mocy n + 1 zbioru {1, 2, … , 2n}. Udowodnić, że 
A zawiera dwie różne liczby a i b takie, że a + b = 2n + 1.
Wskazówka:  n szufladek: do pierwszej można włożyć  1 i 2n, do drugiej 2 i 2n − 1, … , do n-tej: n i n + 1. Wkładamy n +...

Pozostałe 70% treści dostępne jest tylko dla Prenumeratorów

Co zyskasz, kupując prenumeratę?
  • 6 wydań czasopisma "Matematyka"
  • Dostęp do wszystkich archiwalnych artykułów w wersji online
  • Możliwość pobrania materiałów dodatkowych, testów i zadań
  • ...i wiele więcej!
Sprawdź

Przypisy