Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Zasada szufladkowa Dirichleta

No description
by

Jakub Tyrała

on 14 June 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Zasada szufladkowa Dirichleta

Kombinatoryka jest działem matematyki, który pomaga odpowiedzieć na pytania typu: "ile jest możliwych wyników w rzucie monetą?", "Na ile sposobów możemy wybrać delegację dwuosobową z klasy 28 osobowej?", itp.
Aby rozwiązać tego typu zadania, często stosuje się wzory na permutacje, kombinacje, wariacje oraz wariacje z powtórzeniami. Na szczęście nie trzeba pamiętać tych wszystkich wzorów, aby szybko i skutecznie rozwiązywać zadania z kombinatoryki. Do rozwiązania większości zadań w zupełności wystarcza reguła mnożenia i wzór na kombinację.
Co to w ogóle jest?
Zasada szufladkowa Dirichleta


Jest to zasada pozwalająca w prosty i jasny sposób rozwiązać ciekawe problemy matematyczne. Może być wykorzystana podczas rozwiązywania zadań konkursowych. Stopniując jej ogólność możemy przedstawić ją w następujący sposób:

*Jeżeli rozmieścimy 6 królików w pięciu klatkach to w pewnej klatce znajdzie się co najmniej 2 króliki.
*Jeżeli rozmieścimy n przedmiotów w m szufladach to dla n › m w pewnej szufladzie znajduje się co najmniej 2 przedmioty
*Jeżeli rozmieścimy n przedmiotów w m szufladach to dla n › km dla pewnej liczby naturalnej k, to w pewnej szufladzie znajdzie się co najmniej k przedmiotów.

Przykładowe zadanie
Do sklepu przywieziono 25 skrzynek jabłek trzech gatunków. W każdej skrzynce leżały jabłka jednego gatunku. Czy wśród tych skrzynek istnieje dziewięć z jabłkami tego samego gatunku.
Pzrykłady
*W oparciu o zasadę szufladkową nietrudno wykazać, że wśród mieszkańców Warszawy co najmniej dwie osoby mają tę samą liczbę włosów na głowie. Rzeczywiście, liczba włosów na głowie człowieka nie przekracza 500 000, natomiast liczba mieszkańców Warszawy przekracza 1 000 000. Weźmy 500 000 szufladek ponumerowanych kolejnymi liczbami naturalnymi od 1 do 500 000 i wkładajmy do szufladki o danym numerze osoby, które mają taką liczbę włosów na głowie, jak numer szufladki. Ponieważ osób jest ponad 1 000 000, a szufladek 500 000, z naszej zasady wynika, że w jednej lub więcej szufladkach musi się znaleźć więcej niż jedna osoba.

*Analogicznie można wykazać, że w grupie 20 osób muszą być co najmniej dwie, które urodziły się w tym samym miesiącu. Weźmy mianowicie 12 szufladek z nazwami miesięcy i wkładajmy do nich osoby, które urodziły się w danym miesiącu. Ponieważ osób jest 20, a szufladek 12, w jednej z nich muszą być co najmniej dwie osoby.
Zadanie 1
Wykaż, że wśród 6 dowolnych liczb całkowitych istnieją dwie, których różnica jest podzielna przez 5
Peter Gustav Lejeune Dirichlet
Johann Peter Gustav Lejeune Dirichlet (ur. 13 lutego 1805 w Düren, zm. 5 maja 1859 w Getyndze) – niemiecki matematyk francuskiego pochodzenia.

Był wykładowcą uniwersytetów we Wrocławiu, Berlinie i Getyndze. Jego prace dotyczą teorii liczb, szeregów liczbowych, analizy matematycznej, rachunku wariacyjnego i fizyki teoretycznej.

Udowodnił zbieżność szeregu Fouriera (warunki Dirichleta), jest autorem zasady szufladkowej Dirichleta. Jego nazwiskiem została nazwana funkcja charakterystyczna zbioru liczb wymiernych (funkcja Dirichleta), podawana jako standardowy przykład funkcji niecałkowalnej w sensie Riemanna.
Kombinatoryka

Jeżeli wśród przywiezionych skrzynek byłoby jedynie 8 z jabłkami tego samego gatunkun, to nie byłby spełniony warunek odnoszący się do ich całkowitej ilości:
8 · 3 > 25
24 > 25(nieprawda)
Natomiast, jeżeli wśród skrzynek byłoby przynajmniej 9 z jabłkami tego samego gatunku, warunek ten byłby spełniony.
9 · 3 > 25
27 > 25
Odp. Wśród przywiezionych skrzynek istnieje 9 z jabłkami tego samego gatunku.
Czas na zadania !! :D
Wśród dowolnych pięciu liczb znajdą się tylko takie, których reszta z dzielenia przez pięć będzie wynosić 0, 1, 2, 3 lub 4. Jeżeli dobierzemy do nich szóstą liczbę to jej reszta z dzielenia przez pięć będzie taka sama jak przynajmniaj jednej liczby wybranej na początku. Różnica tej liczby i liczby szóstej, będzie podzielna przez 5.
Zadanie 2
Jaką maksymalną liczbę wież można ustawić na szachownicy 8
x 8 tak, aby żadne dwie się nie biły?
Zadanie 3
Mam 49 książek i chcę je rozmieścić na 12 półkach. Ile książek
będzie znajdowało się na jednej półce?

Zadania dodatkowe
Zadanie 1
W szpitalu pracuje 8 lekarzy i 8 pielęgniarek. Na nocnym dyżurze
jest zawsze 1 lekarz i 1 pielęgniarka. Pracujący lekarze mają od 25
do 60 lat, przy czym każdy kolejny lekarz, począwszy do
najmłodszego, jest o 5 lat starszy od poprzedniego. Wiek
pielęgniarek kształtuje się pomiędzy 21 a 35 lat (i są to same liczy
nieparzyste).
Czy można tak ustawić nocne dyżury w szpitalu, aby na każdym
był lekarz i pielęgniarka o innej sumie wieku ?

Wiek pary: lekarz + pielęgniarka kształtuje się od 46 lat (25 + 21)
do 95 lat (60 + 35).
Ilość możliwych par to: 8 x 8 = 64
Ilość możliwych wyników stanowiących sumę wieku pary: lekarz
+ pielęgniarka to 46 (jest 18 wyników, z których każdy raz się
powtarza) 64>46
Jest więcej możliwych zestawień lekarza i pielęgniarki, niż
możliwych do uzyskania liczb, stanowiących sumę ich wieku.
Zatem w szpitalu nie można ustawić nocnych dyżurów w taki
sposób, aby na każdym pracował lekarz i pielęgniarka o innej
sumie wieku. Więc z zasady szufladkowej wynika, że jest 18
dyżurów, w których wiek lekarza i pielęgniarki co najmniej raz się
powtarzają.

Zadanie 2
Mamy 20 worków i 20 kotów. Dla każdego worka i każdego kota
ustalamy cenę, przy czym worek może kosztować od 2zł 10gr do
4zł, a kot od 10zł do 12zł, a ceny są wielokrotnościami 1gr. Czy
można tak ustalić cenę worków i kotów, aby każdy zestaw ,,kot+
worek'' był w innej cenie?

Rozwiązanie:
Cena zestawu ,,kot+worek'' jest z zakresu od 12zł 10gr do 16zł.
Możliwych cen jest 1600-1209=391, natomiast samych
zestawów ,,kot+worek'' jest 20x20=400. Jest więcej zestawów niż możliwych cen, więc pewne 2 zestawy mają tę samą cenę.
Full transcript