Zasada szufladkowa dirchleta - zadania.

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Luxxar
Użytkownik
Użytkownik
Posty: 102
Rejestracja: 3 paź 2010, o 18:00
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 8 razy
Pomógł: 1 raz

Zasada szufladkowa dirchleta - zadania.

Post autor: Luxxar »

Witajcie!
Oto zadania z którymi miałem problem:
1.Udowodnić , że dla każdej liczby całkowitej\(\displaystyle{ k>1}\) istnieje wielokrotność liczby\(\displaystyle{ k}\),
mniejsza od\(\displaystyle{ k^4}\) , którą można zapisać za pomocną co najwyżej czterech
różnych cyfr (w dziesiętnym układzie pozycyjnym).
2. Określamy rekurencyjnie ciąg \(\displaystyle{ {F_n}:F_1=1,F_2=1,F_{n+2}=F_{n+1}+F_n}\).
Udowodnić , że w zbierze \(\displaystyle{ {F_1,F_2,...,F_1000001}}\) istnieje liczba
zakończona co najmniej trzema zerami.
3. Dowieść , że z \(\displaystyle{ (k^2+1)}\)-wyrazowego ciągu różnych liczb rzeczywistych można
wybrać \(\displaystyle{ (k+1)}\) wyrazowy podciąg monotoniczny.

Z góry dziękuję
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Zasada szufladkowa dirchleta - zadania.

Post autor: arek1357 »

Zadanie 2:

Każdemu wyrazowi ciągu Fibonaciego przyporządkujmy jego trzycyfrową końcówkę.
Jeśli cyfr jest mniej dopiszmy z lewej strony zera np:002.

Następnie przyporządkujmy każdej parze liczb:

\(\displaystyle{ A=\left\{ (f_{i},f_{i+1}),i=1,2,3,...10^{6}+1,f_{1}=f_{2}=1 \right\}}\)

przyporządkujmy im pary końcówek.
Par należących do A jest \(\displaystyle{ 10^{6}+1}\), a końcówek jest: 1000.
z tych końcówek można utworzyć jedynie \(\displaystyle{ 10^{6}}\) par.

Z zasady szufladkowej wynika iż w zbirze A istnieją dwie pary wyrazów ciągu Fibonaciego
mające te same końcówki.

załóżmy że są to pary:

\(\displaystyle{ (f_{n},f_{n+1}), (f_{n+k},f_{n+k+1}),n+k \le 10^{6}+1}\)

oznacza to, że:

\(\displaystyle{ 10^{3}|f_{n+k}-f_{n}}\),

oraz:

\(\displaystyle{ 10^{3}|f_{n+k+1}-f_{n+1}}\)

z definicji ciągu Fib...:

\(\displaystyle{ f_{i-1}=f_{i+1}-f_{i}}\)

więc:

\(\displaystyle{ f_{n+k-1}-f_{n-1}=(f_{n+k+1}-f_{n+1}) -(f_{n+k}-f_{n})}\)

co znaczy, że:

\(\displaystyle{ 10^{3}|f_{n+k-1}-f_{n-1}}\)

po iluś tam krokach otrzymamy:

\(\displaystyle{ 10^{3}|f_{k+1}-f_{1}}\)

oraz:

\(\displaystyle{ 10^{3}|f_{k+2}-f_{2}}\)

ale:

\(\displaystyle{ f_{k}=f_{k+2}-f_{k+1}=(f_{k+2}-f_{2})-(f_{k+1}-f_{1})}\)

czyli widać z tego, że:

\(\displaystyle{ 10^{3}|f_{k}}\)



W zadaniu 1 jakby stworzył takie ciągi o długości k+1:

\(\displaystyle{ a,aa,aaa,...,a...a}\)

Ciąg powyższy składa się z k+1 wyrazów., każdej z liczb tego ciągu przyporządkujmy resztę z dzielenia
tej liczby przez k, ciąg ma długość k+1 a reszt jest mniej więc na mocy dirichleta istnieją dwa wyrazy
mające tę samą resztę z dzielenia. Odejmując większą od mniejszej otrzymamy liczbę podzielną przez k
i zapisaną za pomocą dwóch cyfr. Co spełnia warunki zadania.
Późna pora mogłem coś przeoczyć...




W zadaniu 3 cim chyba trzeba skorzystać z uogólnionej wersji zasady szufladkowej.

W sumie 3 cie wydawało mi się najłatwiejsze a tak nie jest.

najpierw liczby rzeczywiste ustawmy w ciąg:

\(\displaystyle{ X=\left\{ a_{1},a_{2},a{3},...,a_{k^{2}},a_{k^{2}+1} \right\}}\)

i teraz utworzyłem taką funkcję:

\(\displaystyle{ f(a_{i})=d(a_{2})}\)

gdzie \(\displaystyle{ d(a_{i})}\) to: długość najdłuższego rosnącego podciągu ciągu:

\(\displaystyle{ \left\{ a_{i}\right\}_{1 \le i \le k^{2}+1}}\), którego pierwszym wyrazem jest \(\displaystyle{ a_{i}}\)

teraz jeśli dla pewnego i:

\(\displaystyle{ f(a_{i}) \ge k+1}\)


to warunek spełniony.
jeśli natomiast:

\(\displaystyle{ f(a_{i}) \le k}\)

to niespełniony , ale:

\(\displaystyle{ |X|=k^{2}+1>k|f(X)|}\)

czyli istnieją:

\(\displaystyle{ i_{1}<i_{2}<...<i_{k+1}}\)

takie, że:

(a) \(\displaystyle{ f(a_{i_{1}})=f(a_{i_{2}})=...=f(a_{i_{k+1}})}\)

si powinny tworzyć ciąg malejący, ale jeśli dla jakiejś pary jest, że:

\(\displaystyle{ a_{i_{s}}<a_{i_{s+1}}}\)

wtedy:

\(\displaystyle{ f(a_{i_{s}})>f(a_{i_{s+1}})}\)

to przeczy (a), itd...
pasowałoby to jakoś bardziej sformalizować.
ale ogólnie idea jest właśnie taka.

Generalnie można to zrobić z twierdzenia Ramsaya, które mówi, że w grafie o wierzchołkach X

kolorujemy go na 2 sposoby czyli np dwie liczby sąsiednie będą tak, że pierwsza mniejsza lub odwrotnie.

krawędzi w takim grafie jest: \(\displaystyle{ 2^{X}}\) a w naszym zadaniu odpowiednio:

\(\displaystyle{ 2^{k^{2}}}\), musi być "klika" o długości k+1,

czyli w naszym przypadku nasz ciąg monotoniczny, coś takiego właśnie !

To tak w skrócie...
Luxxar
Użytkownik
Użytkownik
Posty: 102
Rejestracja: 3 paź 2010, o 18:00
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 8 razy
Pomógł: 1 raz

Zasada szufladkowa dirchleta - zadania.

Post autor: Luxxar »

Witaj , dzięki za odpowiedź.
Wydaje mi się że w drugim zrobiłeś mały błąd ponieważ par jest \(\displaystyle{ 10^6}\)
Zaczynając od \(\displaystyle{ (f_1,f_2),...,(f_{10^6},f_{10^6+1})}\)
Za to mamy 1000 możliwych końcówek , ale nie bierzemy pod uwagę końcówki 000,
gdyż wtedy warunki zadania były by spełnione więc mamy 999 końcówek,
czyli \(\displaystyle{ 999^2}\) par. I dalej się leci.

Pierwsze nie jest udowodnione dla wszystkich liczb całkowitych , tylko dla liczb postaci \(\displaystyle{ aaa(..)aaa}\)

Trzeciego jeszcze nie ogarnąłem.

Pozdrawiam
Luxxar
ODPOWIEDZ