szukanie zaawansowane
 [ Posty: 8 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 30 sty 2015, o 20:03 
Użytkownik

Posty: 20
Lokalizacja: Poznań
Cześć,
Mamy zbiór liczb od 1 do n oraz wiemy, że n \leq 2^{k/2}.
Jak ładnie uzasadnić, że liczba k elementowych podciągów arytmetycznych jest mniej niż n^2 / 2 ?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 30 sty 2015, o 21:36 
Użytkownik
Avatar użytkownika

Posty: 3232
Lokalizacja: blisko
To zadanie trzeba doprecyzować!
Góra
Mężczyzna Offline
PostNapisane: 30 sty 2015, o 22:19 
Użytkownik

Posty: 20
Lokalizacja: Poznań
Już poprawiłem. Bardzo bym prosił o pomoc.
Góra
Mężczyzna Offline
PostNapisane: 31 sty 2015, o 03:14 
Użytkownik
Avatar użytkownika

Posty: 3232
Lokalizacja: blisko
Zauważ, że liczba k elementowych ciągów arytmetycznych o różnicy r znajdujących się w zbiorze:

1,2,3,...,n

jest:

n-(k-1)r=n-kr+r i teraz r \in \left\langle 1;s=\left[  \frac{n-1}{k-1}\right]  \right\rangle

ponieważ 1+(k-1)r \le n


teraz żeby wyliczyć ilość tych ciągów należy zsumować:

\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 1 do n
Góra
Mężczyzna Offline
PostNapisane: 31 sty 2015, o 09:23 
Użytkownik

Posty: 20
Lokalizacja: Poznań
Chodziło o zbiór liczb naturalnych od 1 do n. Jak to teraz można naprawić?
Góra
Mężczyzna Offline
PostNapisane: 31 sty 2015, o 13:35 
Użytkownik
Avatar użytkownika

Posty: 3232
Lokalizacja: blisko
ale co naprawiać ilość ciągów masz zapisanych pod tą sumą, sumę można zwinąć ale nie wiem co chcesz naprawiać?
Góra
Mężczyzna Offline
PostNapisane: 31 sty 2015, o 17:43 
Użytkownik

Posty: 20
Lokalizacja: Poznań
No pytanie było jak udowodnić, żę liczba tych ciągów jest mniejsza od n^2/2, a tego nie napisałeś w ogóle.
Góra
Mężczyzna Offline
PostNapisane: 31 sty 2015, o 19:05 
Użytkownik
Avatar użytkownika

Posty: 3232
Lokalizacja: blisko
Teraz napisałem!

Po zsumowaniu otrzymuję coś takiego:

\frac{1}{2}s\left( 2n-ks-k+s+1\right) - jest to ilość tych ciągów.

gdzie:

s= \left\lfloor \frac{n-1}{k-1} \right\rfloor

i teraz pasuje udowodnić, że:



\frac{1}{2}s\left( 2n-ks-k+s+1\right) \le  \frac{n^2}{2}


Po przekształceniach mamy:

n^2-2sn+ks+ks^2-s^2-s \ge 0


D=4s(2s-ks-k+1)


Wystarczy wykazać, że:

2s-ks-k+1<0

po podstawieniu otrzymamy:



\left\lfloor \frac{n-1}{k-1} \right\rfloor(2-k)< k-1

Jak widać zachodzi to dla k>1

Trzeba tylko sprawdzić dla k=1

Ale dla takiego k=1
ilość takich ciągów jednoelementowych wynosi n

czyli należy sprawdzić czy zachodzi:

n \le  \frac{n^2}{2}

jak widać ono zachodzi dla n \ge 2

nie zachodzi tylko dla n=1


To założenie, że:

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: n=10 , k=3

mamy liczby:

1,2,3,4,5,6,7,8,9,10

teraz wypiszmy wszystkie ciągi trójelementowe arytmetyczne:

123,234,345,456,567,678,789,89(10), tu r=1 jest ich 8

135,246,357,468,579,68(10) tu r=2 jest ich 6

147,258,369,47(10) tu r=3 jest ich 4

159,26(10) tu r=4 jest ich 2

Innych nie ma , razem jest ich:

20< \frac{10^2}{2} - to prawda

Teraz skorzystajmy z mego wzoru na sumę ciągów:

Dane:

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:

\sum_{r=1}^{4}(10-3r+r) = \sum_{r=1}^{4}(10-2r)=8+6+4+2=20

sprawdźmy jeszcze na tym wzorze:

\frac{1}{2}s\left( 2n-ks-k+s+1\right)

n=10 , k=3 , s=4

\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:

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
k - elementowych arytmetycznych w tym zbiorze n - elementowym
jest dla:

k=2 , ale wtedy tych ciągów jest {n \choose 2}= \frac{(n-1)n}{2}

ale to też jest:

\frac{(n-1)n}{2} \le  \frac{n^2}{2}

ale jak widać jest już "dosyć blisko" prawej strony


Zresztą to widać bo funkcja:

f(k)= \sum_{r=1}^{s}(n-kr+r) jest dobrze określona dla k \ge 2 ,

oraz dla k=2 - osiąga maksimum a maksimum jest i tak mniejsze od prawej strony nierwności, którą żeśmy udowodnili bo:

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 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 n

w zbiorze 1,2,3,...,n

n+ \frac{1}{2} \sum_{k=2}^{n}s_{k}\left[ 2n-(k-1)(s_{k}+1)\right]

gdzie:

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!
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 8 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Liczba ciągów długości n i 4 wyrazach.  Tybias  2
 Liczba całkowitych rozwiązań równania  devonsix  4
 liczba elementów antyłańcucha-dowód  MikolajB  0
 Co oznacza, że liczba jest pierwiastkiem z 1 modulo n  matinf  1
 Liczba kombinacji - zadanie 2  Petermus  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl