zasada szufladkowa Dirichleta

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
paulina95
Użytkownik
Użytkownik
Posty: 25
Rejestracja: 4 kwie 2015, o 12:26
Płeć: Kobieta
Lokalizacja: katowice

zasada szufladkowa Dirichleta

Post autor: paulina95 » 4 kwie 2015, o 12:56

zad1
Korzystając z zasady szufladkowej, wykaż, że sposród dowolnych 101 liczb naturalnych wybranych z
przedziału [1, 200] znajdą się:
a) dwie względnie pierwsze;
b) dwie takie, że jedna z nich dzieli drugą.

zad2
Uzasadnij, że ostatnie cyfry wyrazów ciągu Fibonacciego tworzą ciąg okresowy

zad3
Wykaż, że każda liczba naturalna n ma wielokrotność zapisywaną wyłącznie za pomocą zer i siódemek.
Wskazówka: rozważ reszty z dzielenia przez n liczb 7, 77, 777, . . . .

Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 3706
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko

zasada szufladkowa Dirichleta

Post autor: arek1357 » 4 kwie 2015, o 13:35

b). każdą liczbę można przedstawić jako iloczyn potęgi dwójki i nieparzystej:

\(a=2^k(2n+1)\)

W naszym przypadku:

\(0 \le k \le 7\)

\(0 \le n \le 99\)

I teraz każdą taką liczbę wkładamy do szuflady o numerze \(n\)

szuflad jest sto a liczb \(99\) więc będzie dwie liczby postaci:

\(2^is,2^js\)

\(s\) - nieparzysta

Czyli mają wspólny dzielnik cnd.


W przypadku a). łatwo zauważyć, że w \(101\) różnych liczbach wybranych z dwustu

Nie może w rozkładzie na czynniki pierwsze istnieć ten sam dzielnik pierwszy , bo nawet dwójka
jest dzielnikiem dla stu liczb itd...


Zad 3.

\(7,77,777,...,777...7\) tworzymy ciąg \(n+1\) wyrazowy:

Istnieją w tym ciągu dwa wyrazy mające tę samą resztę z dzielenia przez \(n\)

Odejmując większą od mniejszej otrzymamy liczbę podzielną przez \(n\) zapisaną za pomocą siódemek i zer.


Zadanie drugie wyniknie z twierdzenia, które mówi, że:
Każda liczba naturalna różna od zera jest dzielnikiem nieskończenie wielu wyrazów ciągu Fibonacciego.

Np łatwo udowodnić, że wśród jakiś tam początkowych wyrazów ciągu Fibonacciego istnieje taki,
który kończy się czterema zerami!

paulina95
Użytkownik
Użytkownik
Posty: 25
Rejestracja: 4 kwie 2015, o 12:26
Płeć: Kobieta
Lokalizacja: katowice

zasada szufladkowa Dirichleta

Post autor: paulina95 » 6 kwie 2015, o 15:36

czy mógłbyś rozpisać 2 i 3 zadanie? nie bardzo wiem jak to zrobić

Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 3706
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko

zasada szufladkowa Dirichleta

Post autor: arek1357 » 6 kwie 2015, o 18:05

W zadaniu trzecim mamy \(n+1\) liczb

Każdą z tych liczb dzielimy przez \(n\) reszt jest dokładnie \(n\)

Liczb o jedną więcej czyli istnieją dwie liczby, których reszty są identyczne, a więc różnica ich podzielna przez \(n\)

I jak odejmiesz większą od mniejszej to otrzymasz nie dość, że liczbę podzielną przez \(n\)

To ta różnica składa się z tylko siódemek i zer!



W zadaniu drugim poczytaj sobie na temat tej własności ciągu Fibonacciego nie ma sensu rozpisywać od nowa tego! Tu masz na ten temat podobne zadanie:

72399.htm

ODPOWIEDZ