Cześć,
Mamy zbiór liczb od \(\displaystyle{ 1}\) do \(\displaystyle{ n}\) oraz wiemy, że \(\displaystyle{ n \leq 2^{k/2}}\).
Jak ładnie uzasadnić, że liczba \(\displaystyle{ k}\) elementowych podciągów arytmetycznych jest mniej niż \(\displaystyle{ n^2 / 2}\) ?
Liczba k elementowych podciągów arytmetycznych
-
matemaciej
- Użytkownik
- Posty: 20
- Rejestracja: 18 paź 2014, o 13:49
- Płeć: Mężczyzna
- Lokalizacja: Poznań
- Podziękował: 5 razy
Liczba k elementowych podciągów arytmetycznych
Ostatnio zmieniony 30 sty 2015, o 21:19 przez matemaciej, łącznie zmieniany 1 raz.
-
matemaciej
- Użytkownik
- Posty: 20
- Rejestracja: 18 paź 2014, o 13:49
- Płeć: Mężczyzna
- Lokalizacja: Poznań
- Podziękował: 5 razy
-
arek1357
- Użytkownik
- Posty: 5741
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 525 razy
Liczba k elementowych podciągów arytmetycznych
Zauważ, że liczba \(\displaystyle{ k}\) elementowych ciągów arytmetycznych o różnicy \(\displaystyle{ r}\) znajdujących się w zbiorze:
\(\displaystyle{ 1,2,3,...,n}\)
jest:
\(\displaystyle{ n-(k-1)r=n-kr+r}\) i teraz \(\displaystyle{ r \in \left\langle 1;s=\left[ \frac{n-1}{k-1}\right] \right\rangle}\)
ponieważ \(\displaystyle{ 1+(k-1)r \le n}\)
teraz żeby wyliczyć ilość tych ciągów należy zsumować:
\(\displaystyle{ \sum_{r=1}^{s} (n-kr+r)}\)
Tylko ja do końca nie wiem w jakim przedziale znajdują się te ciągi arytmetyczne ja założyłem, że znajdują się w przedziale od \(\displaystyle{ 1}\) do \(\displaystyle{ n}\)
\(\displaystyle{ 1,2,3,...,n}\)
jest:
\(\displaystyle{ n-(k-1)r=n-kr+r}\) i teraz \(\displaystyle{ r \in \left\langle 1;s=\left[ \frac{n-1}{k-1}\right] \right\rangle}\)
ponieważ \(\displaystyle{ 1+(k-1)r \le n}\)
teraz żeby wyliczyć ilość tych ciągów należy zsumować:
\(\displaystyle{ \sum_{r=1}^{s} (n-kr+r)}\)
Tylko ja do końca nie wiem w jakim przedziale znajdują się te ciągi arytmetyczne ja założyłem, że znajdują się w przedziale od \(\displaystyle{ 1}\) do \(\displaystyle{ n}\)
Ostatnio zmieniony 31 sty 2015, o 18:07 przez arek1357, łącznie zmieniany 1 raz.
-
matemaciej
- Użytkownik
- Posty: 20
- Rejestracja: 18 paź 2014, o 13:49
- Płeć: Mężczyzna
- Lokalizacja: Poznań
- Podziękował: 5 razy
Liczba k elementowych podciągów arytmetycznych
Chodziło o zbiór liczb naturalnych od 1 do n. Jak to teraz można naprawić?
-
arek1357
- Użytkownik
- Posty: 5741
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 525 razy
Liczba k elementowych podciągów arytmetycznych
ale co naprawiać ilość ciągów masz zapisanych pod tą sumą, sumę można zwinąć ale nie wiem co chcesz naprawiać?
-
matemaciej
- Użytkownik
- Posty: 20
- Rejestracja: 18 paź 2014, o 13:49
- Płeć: Mężczyzna
- Lokalizacja: Poznań
- Podziękował: 5 razy
Liczba k elementowych podciągów arytmetycznych
No pytanie było jak udowodnić, żę liczba tych ciągów jest mniejsza od \(\displaystyle{ n^2/2}\), a tego nie napisałeś w ogóle.
-
arek1357
- Użytkownik
- Posty: 5741
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 525 razy
Liczba k elementowych podciągów arytmetycznych
Teraz napisałem!
Po zsumowaniu otrzymuję coś takiego:
\(\displaystyle{ \frac{1}{2}s\left( 2n-ks-k+s+1\right)}\) - jest to ilość tych ciągów.
gdzie:
\(\displaystyle{ s= \left\lfloor \frac{n-1}{k-1} \right\rfloor}\)
i teraz pasuje udowodnić, że:
\(\displaystyle{ \frac{1}{2}s\left( 2n-ks-k+s+1\right) \le \frac{n^2}{2}}\)
Po przekształceniach mamy:
\(\displaystyle{ n^2-2sn+ks+ks^2-s^2-s \ge 0}\)
\(\displaystyle{ D=4s(2s-ks-k+1)}\)
Wystarczy wykazać, że:
\(\displaystyle{ 2s-ks-k+1<0}\)
po podstawieniu otrzymamy:
\(\displaystyle{ \left\lfloor \frac{n-1}{k-1} \right\rfloor(2-k)< k-1}\)
Jak widać zachodzi to dla \(\displaystyle{ k>1}\)
Trzeba tylko sprawdzić dla \(\displaystyle{ k=1}\)
Ale dla takiego \(\displaystyle{ k=1}\)
ilość takich ciągów jednoelementowych wynosi \(\displaystyle{ n}\)
czyli należy sprawdzić czy zachodzi:
\(\displaystyle{ n \le \frac{n^2}{2}}\)
jak widać ono zachodzi dla \(\displaystyle{ n \ge 2}\)
nie zachodzi tylko dla \(\displaystyle{ n=1}\)
To założenie, że:
\(\displaystyle{ n \le 2^{ \frac{k}{2} }}\) jest zupełnie niepotrzebne a wręcz przeszkadza.
I narobiło od początku trochę zamieszania!
zauważ przykład pokaże ci jak to działa:
niech: \(\displaystyle{ n=10 , k=3}\)
mamy liczby:
\(\displaystyle{ 1,2,3,4,5,6,7,8,9,10}\)
teraz wypiszmy wszystkie ciągi trójelementowe arytmetyczne:
\(\displaystyle{ 123,234,345,456,567,678,789,89(10),}\) tu \(\displaystyle{ r=1}\) jest ich \(\displaystyle{ 8}\)
\(\displaystyle{ 135,246,357,468,579,68(10)}\) tu \(\displaystyle{ r=2}\) jest ich \(\displaystyle{ 6}\)
\(\displaystyle{ 147,258,369,47(10)}\) tu \(\displaystyle{ r=3}\) jest ich \(\displaystyle{ 4}\)
\(\displaystyle{ 159,26(10)}\) tu \(\displaystyle{ r=4}\) jest ich \(\displaystyle{ 2}\)
Innych nie ma , razem jest ich:
\(\displaystyle{ 20< \frac{10^2}{2}}\) - to prawda
Teraz skorzystajmy z mego wzoru na sumę ciągów:
Dane:
\(\displaystyle{ n=10 , k=3 , s= \left\lfloor \frac{n-1}{k-1} \right\rfloor= \left\lfloor \frac{9}{2} \right\rfloor = \left\lfloor 4,5 \right\rfloor =4}\)
Podstawmy:
\(\displaystyle{ \sum_{r=1}^{4}(10-3r+r) = \sum_{r=1}^{4}(10-2r)=8+6+4+2=20}\)
sprawdźmy jeszcze na tym wzorze:
\(\displaystyle{ \frac{1}{2}s\left( 2n-ks-k+s+1\right)}\)
\(\displaystyle{ n=10 , k=3 , s=4}\)
\(\displaystyle{ \frac{1}{2} \cdot4 \cdot \left( 2 \cdot 10-3 \cdot 4-3+4+1\right)=2 \cdot \left( 20-12-3+5\right)=2 \cdot 10=20}\)
Wyszło tyle samo wszędzie czyli to działa czyli mamy:
\(\displaystyle{ 10>2^{ \frac{3}{2}} , k=3}\)
a nie na odwrót!
Jest to bardzo mocna nierówność!!!
Jeszcze jedno spostrzeżenie wydaje mi się choć tego nie sprawdzałem, że maksymalna liczba ciągów
\(\displaystyle{ k}\) - elementowych arytmetycznych w tym zbiorze \(\displaystyle{ n}\) - elementowym
jest dla:
\(\displaystyle{ k=2}\) , ale wtedy tych ciągów jest \(\displaystyle{ {n \choose 2}= \frac{(n-1)n}{2}}\)
ale to też jest:
\(\displaystyle{ \frac{(n-1)n}{2} \le \frac{n^2}{2}}\)
ale jak widać jest już "dosyć blisko" prawej strony
Zresztą to widać bo funkcja:
\(\displaystyle{ f(k)= \sum_{r=1}^{s}(n-kr+r)}\) jest dobrze określona dla \(\displaystyle{ k \ge 2}\) ,
oraz dla \(\displaystyle{ k=2}\) - osiąga maksimum a maksimum jest i tak mniejsze od prawej strony nierwności, którą żeśmy udowodnili bo:
\(\displaystyle{ f_{max}(k)=f(2)= \frac{(n-1)n}{2} \le \frac{n^2}{2}}\) - co od razu widać
ten dowód jest znacznie szybszy niż tamten z deltą i można było tak od razu, a potem jeszcze sprawdzić dla \(\displaystyle{ k=1}\) - jak wyżej zrobiłem.
No ale za to są dwa dowody!
A tak wygląda wzór na sumę wszystkich ciągów arytmetycznych o długości od jeden do \(\displaystyle{ n}\)
w zbiorze \(\displaystyle{ 1,2,3,...,n}\)
\(\displaystyle{ n+ \frac{1}{2} \sum_{k=2}^{n}s_{k}\left[ 2n-(k-1)(s_{k}+1)\right]}\)
gdzie:
\(\displaystyle{ s_{k}=\left\lfloor \frac{n-1}{k-1} \right\rfloor}\)-- 2 lutego 2015, 12:30 --Zakładam, że ciąg arytmetyczny może być jednoelementowy lub dwuelementowy!
Po zsumowaniu otrzymuję coś takiego:
\(\displaystyle{ \frac{1}{2}s\left( 2n-ks-k+s+1\right)}\) - jest to ilość tych ciągów.
gdzie:
\(\displaystyle{ s= \left\lfloor \frac{n-1}{k-1} \right\rfloor}\)
i teraz pasuje udowodnić, że:
\(\displaystyle{ \frac{1}{2}s\left( 2n-ks-k+s+1\right) \le \frac{n^2}{2}}\)
Po przekształceniach mamy:
\(\displaystyle{ n^2-2sn+ks+ks^2-s^2-s \ge 0}\)
\(\displaystyle{ D=4s(2s-ks-k+1)}\)
Wystarczy wykazać, że:
\(\displaystyle{ 2s-ks-k+1<0}\)
po podstawieniu otrzymamy:
\(\displaystyle{ \left\lfloor \frac{n-1}{k-1} \right\rfloor(2-k)< k-1}\)
Jak widać zachodzi to dla \(\displaystyle{ k>1}\)
Trzeba tylko sprawdzić dla \(\displaystyle{ k=1}\)
Ale dla takiego \(\displaystyle{ k=1}\)
ilość takich ciągów jednoelementowych wynosi \(\displaystyle{ n}\)
czyli należy sprawdzić czy zachodzi:
\(\displaystyle{ n \le \frac{n^2}{2}}\)
jak widać ono zachodzi dla \(\displaystyle{ n \ge 2}\)
nie zachodzi tylko dla \(\displaystyle{ n=1}\)
To założenie, że:
\(\displaystyle{ n \le 2^{ \frac{k}{2} }}\) jest zupełnie niepotrzebne a wręcz przeszkadza.
I narobiło od początku trochę zamieszania!
zauważ przykład pokaże ci jak to działa:
niech: \(\displaystyle{ n=10 , k=3}\)
mamy liczby:
\(\displaystyle{ 1,2,3,4,5,6,7,8,9,10}\)
teraz wypiszmy wszystkie ciągi trójelementowe arytmetyczne:
\(\displaystyle{ 123,234,345,456,567,678,789,89(10),}\) tu \(\displaystyle{ r=1}\) jest ich \(\displaystyle{ 8}\)
\(\displaystyle{ 135,246,357,468,579,68(10)}\) tu \(\displaystyle{ r=2}\) jest ich \(\displaystyle{ 6}\)
\(\displaystyle{ 147,258,369,47(10)}\) tu \(\displaystyle{ r=3}\) jest ich \(\displaystyle{ 4}\)
\(\displaystyle{ 159,26(10)}\) tu \(\displaystyle{ r=4}\) jest ich \(\displaystyle{ 2}\)
Innych nie ma , razem jest ich:
\(\displaystyle{ 20< \frac{10^2}{2}}\) - to prawda
Teraz skorzystajmy z mego wzoru na sumę ciągów:
Dane:
\(\displaystyle{ n=10 , k=3 , s= \left\lfloor \frac{n-1}{k-1} \right\rfloor= \left\lfloor \frac{9}{2} \right\rfloor = \left\lfloor 4,5 \right\rfloor =4}\)
Podstawmy:
\(\displaystyle{ \sum_{r=1}^{4}(10-3r+r) = \sum_{r=1}^{4}(10-2r)=8+6+4+2=20}\)
sprawdźmy jeszcze na tym wzorze:
\(\displaystyle{ \frac{1}{2}s\left( 2n-ks-k+s+1\right)}\)
\(\displaystyle{ n=10 , k=3 , s=4}\)
\(\displaystyle{ \frac{1}{2} \cdot4 \cdot \left( 2 \cdot 10-3 \cdot 4-3+4+1\right)=2 \cdot \left( 20-12-3+5\right)=2 \cdot 10=20}\)
Wyszło tyle samo wszędzie czyli to działa czyli mamy:
\(\displaystyle{ 10>2^{ \frac{3}{2}} , k=3}\)
a nie na odwrót!
Jest to bardzo mocna nierówność!!!
Jeszcze jedno spostrzeżenie wydaje mi się choć tego nie sprawdzałem, że maksymalna liczba ciągów
\(\displaystyle{ k}\) - elementowych arytmetycznych w tym zbiorze \(\displaystyle{ n}\) - elementowym
jest dla:
\(\displaystyle{ k=2}\) , ale wtedy tych ciągów jest \(\displaystyle{ {n \choose 2}= \frac{(n-1)n}{2}}\)
ale to też jest:
\(\displaystyle{ \frac{(n-1)n}{2} \le \frac{n^2}{2}}\)
ale jak widać jest już "dosyć blisko" prawej strony
Zresztą to widać bo funkcja:
\(\displaystyle{ f(k)= \sum_{r=1}^{s}(n-kr+r)}\) jest dobrze określona dla \(\displaystyle{ k \ge 2}\) ,
oraz dla \(\displaystyle{ k=2}\) - osiąga maksimum a maksimum jest i tak mniejsze od prawej strony nierwności, którą żeśmy udowodnili bo:
\(\displaystyle{ f_{max}(k)=f(2)= \frac{(n-1)n}{2} \le \frac{n^2}{2}}\) - co od razu widać
ten dowód jest znacznie szybszy niż tamten z deltą i można było tak od razu, a potem jeszcze sprawdzić dla \(\displaystyle{ k=1}\) - jak wyżej zrobiłem.
No ale za to są dwa dowody!
A tak wygląda wzór na sumę wszystkich ciągów arytmetycznych o długości od jeden do \(\displaystyle{ n}\)
w zbiorze \(\displaystyle{ 1,2,3,...,n}\)
\(\displaystyle{ n+ \frac{1}{2} \sum_{k=2}^{n}s_{k}\left[ 2n-(k-1)(s_{k}+1)\right]}\)
gdzie:
\(\displaystyle{ s_{k}=\left\lfloor \frac{n-1}{k-1} \right\rfloor}\)-- 2 lutego 2015, 12:30 --Zakładam, że ciąg arytmetyczny może być jednoelementowy lub dwuelementowy!