Definicje: Jeżeli mamy n+1 przedmiotów i n szufladek to 2 przedmioty muszą trafić do jednej z szuflad



Pobieranie 10.33 Kb.
Data27.04.2016
Rozmiar10.33 Kb.

Zasada Szufladkowa Dirichleta – podsumowanie kółka


  1. Definicje:

  • Jeżeli mamy n+1 przedmiotów i n szufladek to 2 przedmioty muszą trafić do jednej z szuflad;

  • Jeśli mamy n przedmiotów i k szuflad to przedmiotów musi trafić do jednej z szuflad;

  1. Wyjaśnienia symboli:

  • Kwantyfikator ogólny („dla każdego”): -> dla każdego x zachodzi dana własność;

  • Kwantyfikator szczegółowy („istnieje jakiś element”): -> istnieje taki x, dla którego zachodzi dana własność;

  • Sufit (zaokrąglenie w górę) : np.: ;

  • Zbiór reszt z dzielenia przez n zazwyczaj oznacza się przez : ;

  • Gdy zachodzi potrzeba użycia więcej niż kilku (np. trzech) zmiennych (literek) to warto posługiwać się indeksami, np.: zamiast pisać : a, b, c często wygodniej jest zapisać: a1, a2, a3; W szczególności, gdy mamy do czynienia z nieznaną ilością elementów, przykładowo:

Zbiór A złożony z n nieznanych elementów zapiszemy następująco: A = { a1,a2,a3,…, an } ;

  • Gdy liczby a i b dają taką samą resztę z dzielenia przez n zapisujemy:

  1. Zadania przerobione w trakcie zajęć z rozwiązaniami:

(Słownie: zbiór A składa się z dowolnych 5 liczb (x1,…,x5) naturalnych takich, że istnieją pewne dwie (dlatego y1, y2) spośród tych pięciu dających taką samą resztę z dzielenia (po lewej str. strzałki założenie, po prawej teza)

Dowód:

Niech Z4 oznacza zbiór reszt z dzielenia przez 4 , wtedy : Z4 = {0,1,2,3}.



(Każda z podanych wyżej reszt (elementów zbioru Z4 ) to nasza „szufladka”.)

Co oczywiste, każda liczba naturalna daje pewną resztę z dzielenia przez 4.

Niech zmienne s1,s2,s3,s4 oznaczają nasze szufladki.

Przypiszmy liczbę x1 do szufladki s1 (nie znamy wartości liczby x1 , zatem nie możemy stwierdzić, czy jej reszta z dzielenia przez 4 wynosi 0,1,2 czy 3, ale na pewno jakąś daje, dlatego oznaczamy szufladki jak wyżej) .

Jeśli liczba x2 będzie dawać taką samą resztę z dzielenia co x1 to spełniona będzie teza, dlatego załóżmy, że x2 w wyniku dzielenia przez 4 daje inną resztę niż x1 i dlatego przypisujemy ją do szufladki s2.

Postępując analogicznie dla liczb x3 i x4 zauważymy, że każda z szufladek (s1,s2,s3,s4) ma już po jednym elemencie, a musimy przyporządkować do którejkolwiek element x5, zatem będzie istnieć pewna szufladka, w której będą 2 elementy. C.N.D.



  • * Danych jest 111 dodatnich liczb całkowitych. Wykaż, że spośród nich można wybrać 11 takich liczb, których suma jest podzielna przez 11.

Z: A={ a1,a2,…,a111: a1,a2,…,a111 } ->zbiór 111 dodatnich liczb całkowitych;

T: , że 11 | (b1 + b2 + … + b11) (słownie: istnieje 11 liczb (spośród tych 111) takich, że ich suma jest podzielna przez 11);

Dowód:

Niech Z11 oznacza zbiór reszt z dzielenia przez 11: Z11 = {0,1,…,10} ; (Każda z tych reszt z dzielenia to nasza „szufladka”, „przedmioty” to dane 111 liczb )



Zgodnie z Z.S.D. do jednej z szuflad trafi : przedmiotów.

Zatem widzimy, że istnieje 11 liczb dających tą samą resztę z dzielenia, nazwijmy ją

Oznaczmy elementy tej szuflady: b1,b2,…,b11 i zauważmy, że:

b1 = 11k1 + r , b2 = 11k2 + r ,… , b11 = 11k11 + r , przy założeniu, że : k1 , k2 , … , k11

Ponadto definiujemy S = b1 + b2 + … + b11 , jako sumę elementów tej szuflady.

Dla tak przyjętych oznaczeń mamy: S = b1 + b2 + … + b11 -> S = (11k1 + r) + (11k2 + r) + … + (11k11 + r) -> S = 11(k1+ k2 + … + k11) + 11r -> S = 11(k1+ k2 + … + k11 + r) -> 11 | S



C.N.D.

Koło Matematyczne III LO w Białymstoku


©absta.pl 2016
wyślij wiadomość

    Strona główna