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ę
Zasada szufladkowa dirchleta - zadania.
- arek1357
- 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.
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...
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...
-
- 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.
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
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