mat02_zeszyt_cwiczen_dla_ucznia.doc

Zeszyt ćwiczeń

SKRZYNKA Z NARZĘDZIAMI MŁODEGO KOMBINATORYKA

Paweł Naroski

ZADANIA

1.         Ze zbioru {1,..., 2n} wybieramy n+1 różnych liczb. Pokazać, że zawsze wśród tych liczb znajduje się para liczb, których suma wynosi 2n + 1.

2.         Ze zbioru {1,..., 2n} wybieramy n+1 różnych liczb. Pokazać, że zawsze wśród tych liczb znajduje się para liczb względnie pierwszych.

3.         W pewnym sklepie znajduje się sześć słojów wypełnionych galaretkami w ośmiu kolorach. Jest dokładnie dwadzieścia galaretek w każdym ko­lorze. Wykaż, że istnieje słój, który zawiera co najmniej dwie galaretki w kolorze x i co najmniej dwie galaretki w kolorze y dla pewnych dwóch różnych kolorów x i y.

4.         Niech p będzie liczbą naturalną dodatnią. Weźmy dowolnych p liczb całkowitych a1, . . . ,ap. Pokazać, że suma pewnych spośród tych liczb jest podzielna przez p.

5.         Niech a1, . . . , a9 będą nieujemnymi liczbami naturalnymi takimi, że Sai= 90, czyli po prostu dziewięcioma liczbami, które sumują się do 90. Wykazać, że pewne trzy spośród tych liczb sumują się do co najmniej 30, a pewne cztery spośród nich sumują się do co najmniej 40.

6.         Robin Hood strzelił z łuku siedem razy do okrągłej tarczy o promieniu jednego łokcia. Lady Marion oglądając popisy Robina stwierdziła, że każde dwie strzały spośród tkwiących w tarczy są oddalone od siebie o co najmniej łokieć. Wykazać, że Robin jedną ze strzał trafił w sam środek tarczy. (Oczywiście pewnikiem w tym zadaniu jest, że Robin każdą wystrzeloną strzałą trafił w tarczę.)

7.         Na teście wyboru złożonym z 20 pytań obowiązywały takie zasady, że za zaznaczenie w danym pytaniu poprawnej odpowiedzi otrzymuje się 1 punkt, za zaznaczenie błędnej odpowiedzi otrzymuje się -1 punkt, a za pozostawienie pytania niezaznaczonego otrzymuje się 0 punktów. Pe­wien student zaznaczył jakąś odpowiedź w każdym pytaniu, po spraw­dzeniu wyników okazało się, że otrzymał 15 punktów. Wykaż, że przy sprawdzaniu testu musiał wystąpić jakiś błąd.

8.     Grupa uczniów usiadła wokół okrągłego stołu tak, że po obu stronach każdej dziewczyny siedzą chłopcy, a po obu stronach każdego chłopca siedzą dziewczyny. Pokazać, że w rozważanej grupie liczba dziewczyn jest równa liczbie chłopców.

9.     Wykazać, że jest niemożliwym, aby konik szachowy startując z danego pola przebył wszystkie pola szachownicy wymiaru n x n, każde z nich odwiedzając dokładnie raz oraz wracając na koniec na pole, z którego startował w przypadku, gdy n jest nieparzyste i większe niż 1.

10.     Zbadać czy istnieją liczby niewymierne x i y takie, że xy jest liczbą wymierną.

11.    W grupie 15 osób jest 7, które gra na skrzypcach, 10, które gra na altówce i 6, które gra na wiolonczeli. Wśród tych osób 3 umie grać zarówno na skrzypcach i wiolonczeli. Tyle samo osób gra zarówno na skrzypcach, jak i altówce. W końcu 2 osoby grają na tych wszystkich trzech instrumentach. Ile osób w tej grupie umie grać na altówce i wiolonczeli? Zakładamy, że każda osoba z rozważanej grupy gra na co najmniej jednym z wymienionych instrumentów.

12.     Ile jest liczb naturalnych dodatnich mniejszych od 70, które są względ­nie pierwsze z 70?

13.     Na ile sposobów można otrzymać pięć kart z talii dwudziestu czterech tak, aby wśród nich był co najmniej jeden as, co najmniej jeden król, co najmniej jedna dama i co najmniej jeden walet?

14.     Na ile sposobów można ustawić w ciąg cyfry 0,...,9 tak, aby pierwsza z nich była większa od 2, a ostatnia mniejsza od 9?

15.     Ile jest liczb czterocyfrowych takich, które zawierają przynajmniej jed­no 0, przynajmniej jedną 1 i przynajmniej jedną 2?

ROZWIĄZANIA

Uwaga! Zaglądanie na następne strony grozi zepsuciem zabawy z rozwiązywania zadań zawartych w tym zeszycie ćwiczeń :).

1.   
Ze zbioru {1,..., 2n} wybieramy n+1 różnych liczb. Pokazać, że zawsze wśród tych liczb znajduje się para liczb, których suma wynosi 2n + 1.

Wybieramy ze zbioru {1,..., 2n} dowolne n+1 różnych liczb a1,.. .,an+1

Rozważmy n szufladek Si dla i = 1,..., n. Na szufladce Si napiszmy dwie liczby: i oraz 2n + 1 — i. Te dwie liczby są różne, gdyż pierwsza z nich jest nie większa od n, a druga jest większa od n. Zauważmy też, że każda liczba ze zbioru {1,..., 2n} jest napisana na dokładnie jednej szufladce.

Umieśćmy teraz wybrane liczby a1,..., an+1 w szufladkach w ten spo­sób, że każda liczba trafia do tej szufladki, na której jest napisana. Liczb jest n + 1, a szufladek n, więc z zasady szufladkowej otrzymuje­my, iż w pewnej szufladce Sj znajdują się dwie liczby. Zgodnie z regułą umieszczania liczb w szufladkach te liczby to j i 2n + 1 — j, a przecież  j + (2n + 1 -j) = 2n+1.

2.    Ze zbioru {1,..., 2n} wybieramy n+1 różnych liczb. Pokazać, że zawsze wśród tych liczb znajduje się para liczb względnie pierwszych.

Wybieramy ze zbioru {1,..., 2n} dowolne n+1 różnych liczb a1,.. .,an+1.

Rozważmy n szufladek Si  dla i = 1,... ,n. Na szufladce Si napiszmy dwie liczby: 2i — 1 oraz 2i. Napisane liczby są różne i każda liczba ze zbioru {1,..., 2n} jest napisana na dokładnie jednej szufladce.

Umieśćmy teraz wybrane liczby w szufladkach w ten spo­sób, że każda liczba trafia do tej szufladki, na której jest napisana. Liczb jest n + 1, a szufladek n, więc z zasady szufladkowej otrzymuje­my, iż w pewnej szufladce Sj znajdują się dwie liczby. Zgodnie z regułą umieszczania liczb w szufladkach te liczby to
2j-1 i 2j.

Pokażemy, że te liczby są względnie pierwsze. Niech d będzie dowolnym wspólnym dzielnikiem obu liczb 2j-1 oraz 2j. Skoro tak, to d dzieli również różnicę tych liczb, czyli d dzieli 2j - (2j - 1) = 1. Jedynym dzielnikiem liczby 1 jest ona sama, a więc d = 1. Ale d było dowolnie wybranym dzielnikiem liczb 2j-1 oraz 2j, a więc 1 jest jedynym dziel­nikiem tych liczb i tym samym są one względnie pierwsze. (Zauważmy, że powyższy argument będzie działał również wtedy, gdy rozważane dwie liczby będą postaci 2j i 2j + 1, po prostu prawdziwe jest ogól­niejsze twierdzenie, że każde dwie kolejne liczby naturalne są względnie pierwsze.)

3.    W pewnym sklepie znajduje się sześć słojów wypełnionych galaretkami w ośmiu kolorach. Jest dokładnie dwadzieścia galaretek w każdym ko­lorze. Wykaż, że istnieje słój, który zawiera co najmniej dwie galaretki w kolorze x i co najmniej dwie galaretki w kolorze y dla pewnych dwóch różnych kolorów xi y.

Słojów jest sześć, a galaretek w dowolnym, ustalonym kolorze k jest dwadzieścia, więc z zasady szufladkowej istnieje taki słój, który zawiera co najmniej dwie galaretki w kolorze k. Niech Ck oznacza numer słoja, który zawiera co najmniej dwie galaretki w kolorze k. (Takich słojów może być więcej niż jeden, w takim wypadku Ck oznacza dowolny z nich.)

Mamy osiem liczb Ck - każdą dla innego koloru. Ale możliwych wartości dla tych liczb jest jedynie sześć, gdyż tyle jest słojów, a więc korzystając ponownie z zasady szufladkowej otrzymujemy, iż dwie spośród tych liczb są sobie równe, czyli istnieją dwa takie kolory x i y, x≠ y, że cx = cy =: j. A to oznacza, że w jednym słoju, tym o numerze j, znajdują się co najmniej dwie galaretki w kolorze x i co najmniej dwie galaretki w kolorze y.

(Dodatkowe zadanie: dla obu zastosowań zasady szufladkowej w po­wyższym rozwiązaniu, wskaż, które obiekty były szufladkami, a które skarpetkami.)

4.   Niech p będzie liczbą naturalną dodatnią. Weźmy dowolnych p liczb całkowitych a1, . . . ,ap . Pokazać, że suma pewnych spośród tych liczb jest po dzielna przez p.

Weźmy p sum a1, a1+a2,…,a1+…+ap czyli sumy pierwszych i spośród wybranych liczb, gdzie i =1,... ,p. Rozważmy reszty z dziele­nia tych sum przez p. Jeśli taka reszta z dzielenia przez p którejkolwiek z nich jest równa 0, to oznacza, że dana suma jest podzielna przez p. Załóżmy zatem, iż każda taka reszta jest różna od 0. To oznacza, że każda z nich należy do zbioru {1,... ,p — 1}. Ponieważ sum jest p, a możliwych reszt p — 1, zatem z zasady szufladkowej otrzymujemy, iż pewne dwie sumy, powiedzmy a1 + ... +ai oraz a1 + ... + aj, gdzie i < j, dają taką samą resztę a przy dzieleniu przez p. To oznacza, że te sumy daje się przedstawić w postaci a1 + ... +ai= ki* p + a oraz a1 +... + aj = kj*p + a, gdzie kiikj są pewnymi liczbami całkowitymi. A tym samym

              ai+1+…aj=(a1+…aj)-(a1+…+ai)=(kj*p + a)-(ki* p + a)=(kj-ki)*p

co oznacza, że suma ai+1 + ... + aj jest po dzielna przez p.

5.   Niecha1, . . . , a9 będą nieujemnymi liczbami naturalnymi takimi, że, Ʃai= 90 czyli po prostu dziewięcioma liczbami, które sumują się do 90. Wykazać, że pewne trzy spośród tych liczb sumują się do co najmniej 30, a pewne cztery spośród nich sumują się do co najmniej 40.

Każdą liczbę naturalną n możemy sobie wyobrażać jako pojemnik, w którym znajduje się dokładnie n piłeczek. Sumę danych liczb otrzy­mujemy wtedy wsypując piłeczki reprezentujące składniki do jednego pojemnika.

Rozważmy w ten sposób trzy pojemniki odpowiadające liczbom a1 + a2 + a3, a...