szukanie zaawansowane
 [ Posty: 12 ] 
Autor Wiadomość
Mężczyzna Online
PostNapisane: 10 maja 2018, o 22:14 
Użytkownik
Avatar użytkownika

Posty: 16
Lokalizacja: Warszawa
Witam,

Chciałbym udowodnić coś bardzo intuicyjnego w jak najkrótszy sposób (najchętniej nie korzystając z indukcji, ale nie znalazłem lepszego działu). Nie jest to trudne, ale wydaje mi się, że tak prosty lemat można sprowadzić do 2-3 zdań :P

Niech będzie dane n. Udowodnić, że każde k, takie że 1  \le k  \le 1 + 2 + ... + n można przedstawić jako sumę wybranych liczb ze zbioru \left\{ 1, 2, 3, ..., n \right\}, przy czym wykorzystując każdy element maksymalnie raz.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Online
PostNapisane: 10 maja 2018, o 23:14 
Użytkownik

Posty: 12039
Ja nie widzę prostszego argumentu niż indukcja po k\ge 1, \ k\le 1+2+\ldots+n.
Powiedzmy, że przedstawiliśmy liczbę k, \ 1\le k<1+2+\ldots+n w postaci sumy parami różnych elementów zbioru \left\{ 1,2, \ldots n\right\}. Pokażemy, że liczbę k+1 możemy wówczas również przedstawić w takiej formie.
Niech więc
k=a_1+a_2+\ldots+a_m, gdzie a_i \in \left\{ 1, \ldots n\right\} oraz a_1<a_2<\ldots<a_m. Jeżeli a_m<n, to a_{m}+1\in\left\{ 1, \ldots n\right\} i po prostu mamy k+1=a_1+a_2+\ldots+a_{m-1}+(a_m+1), natomiast jeżeli a_m=n, to istnieje liczba j \in \left\{ 1,2, \ldots n\right\}, która nie wystąpiła w sumie k=a_1+a_2+\ldots+a_m (bo nieprawda, że 1+2+\ldots+n<1+2+\ldots+n i każda liczba w reprezentacji k miała wystąpić najwyżej raz). Weźmy taką konkretną j. Niech więc liczby a_s, a_t z reprezentacji k będą takie, że a_s=\max\left\{ a_i: a_i<j\right\} , a_t=\min\left\{ a_i: a_i>j\right\}. Wówczas a_s+1\le j, \ a_s+1\in \left\{ 1,2 , \ldots n\right\} oraz a_s+1 nie występuje w reprezentacji k, więc skoro
k=a_1+\ldots+a_s+a_t+\ldots+a_m, to mamy, po zastąpieniu w tej sumie a_s przez a_s+1,
k+1=a_1+\ldots+a_{s-1}+(a_s+1)+a_t+\ldots+a_m. Uff.

Teraz wystarczy odnotować, że dla k=1 takie przedstawienie (po prostu w postaci samej jedynki) istnieje i powołać się na zasadę indukcji matematycznej.

-- 10 maja 2018, o 22:46 --

Chociaż tak jak patrzę, to chyba mam nieco prostszy pomysł:
popatrzmy na tę sumę 1+2+\ldots+n.
Jest to oczywiście przedstawienie liczby 1+2+\ldots+n w pożądanej postaci. Teraz zauważmy, że możemy wykreślić dokładnie jedną z liczb z tej sumy, by uzyskać reprezentację którejś z liczb spośród
(1+2+\ldots+n)-k, gdzie k przebiega zbiór \left\{ 1,2, \ldots n\right\}, dokładnie dwie liczby, aby uzyskać reprezentację w pożądanej przez nas postaci którejś z liczb
(1+2+\ldots+n)-(1+2), \ldots (1+2+\ldots+n)-(n+n-1) i ogólniej dokładnie \eta liczb, \ \eta \in \left\{ 1, 2, \dots n-1\right\} otrzymując w ten sposób dowolną spośród liczb
(1+2+\ldots+n)-(1+2+\ldots+\eta), \ldots (1+2+\ldots+n)- ((n-\eta+1)+\ldots+n) (malejąco).
Pozostaje zauważyć, że
(1+2+\ldots+n)-(1+2+\ldots+\eta+1)\ge (1+2+\ldots+n)-\left(( n-\eta+1)+\ldots+n\right)  \Leftrightarrow \\ \Leftrightarrow  2n-\eta+1\ge \eta+2 \Leftrightarrow \eta< n-\frac 1 2,
co oczywiście zawsze zachodzi, gdy \eta\in \left\{ 1,2, \ldots n-1\right\}.

To jest sprytniejsze, niźli poprzednie podejście, ale pewnie jakoś nieścisłe. :(
Góra
Mężczyzna Online
PostNapisane: 10 maja 2018, o 23:52 
Użytkownik
Avatar użytkownika

Posty: 16
Lokalizacja: Warszawa
Niech ktoś to nazwie twierdzeniem + [tu wstaw nazwisko (w dopełniaczu) ochotnika]. Już któryś raz potrzebuję lematu o indukcyjnym tworzeniu liczb jako sumy mniejszych (w bardzo różnych wariacjach i zadaniach te twierdzenia).

W każdym razie, dzięki za pomoc!
Góra
Mężczyzna Offline
PostNapisane: 11 maja 2018, o 14:32 
Gość Specjalny
Avatar użytkownika

Posty: 2666
Lokalizacja: Warszawa
A może tak zapisać - liczby postaci k = 1 + 2 + ... + j mają trywialne przedstawienie w postaci szukanej sumy.

Dla pozostałych liczb - istnieje 1 \le j \le n-1, takie że 1 + 2 + ... + j < k < 1 + 2 + ... + j + (j+1).

Skupmy się na tym, ile k brakuje do większej z tych sum - niech r=1 + 2 + ... + j + (j+1) - k.

Wówczas 1 \le r \le j.

Zatem k=1 + 2 + ... + j + (j+1) - r, czyli wśród liczb \lbrace 1, 2, ..., j, j+1 \rbrace pomijamy jedynie jedną liczbę r i mamy poszukiwane przedstawienie.
Góra
Mężczyzna Online
PostNapisane: 11 maja 2018, o 14:44 
Użytkownik

Posty: 12039
O! To jest właśnie różnica między sztuką a rzemiosłem, widać ją nawet w tak prostym zadaniu.
Góra
Mężczyzna Offline
PostNapisane: 11 maja 2018, o 14:49 
Gość Specjalny
Avatar użytkownika

Posty: 2666
Lokalizacja: Warszawa
Inspirowane Twoim drugim sposobem :)
Góra
Mężczyzna Offline
PostNapisane: 11 maja 2018, o 15:37 
Użytkownik

Posty: 14863
Lokalizacja: Bydgoszcz
A przecież indukcyjnie idzie tak prosto:
Dla n=2 sprawdzamy na palcach.
Załóżmy, że każda liczba od 1 do 1+\dots+n ma szukane przedstawienia.
Weźmy dowolną liczbę nie większą od 1+\dots+n+(n+1). Jeżeli jest mniejsza lub równa niż 1+\dots+n to przedstawienie istnieje na mocy założenia. A jeżeli jest większa, to jest postaci (n+1)+k, gdzie k jest nie większe niż 1+\dots+n wiec ...
Góra
Mężczyzna Offline
PostNapisane: 11 maja 2018, o 22:00 
Użytkownik
Avatar użytkownika

Posty: 1428
Lokalizacja: Katowice
dzielimy k z resztą przez n+1 i otrzymujemy k=a\cdot(n+1)+r przy czym 0\le r \le n oraz a\le \frac n2 (gdyż k \le 1+2+\ldots+n = \frac n2 (n+1))

wobec tego

k=r+\underbrace{(n+1)+(n+1)+\ldots+(n+1)}_{a \text{ razy}}

i każdą z a liczb n+1 zapisujemy w postaci j+(n+1-j) dla parami różnych j dbając o to, by j \neq r \neq n+1-j (co da się zrobić ze względu na szacowanie a\le \frac n2)
Góra
Mężczyzna Online
PostNapisane: 14 maja 2018, o 19:54 
Użytkownik
Avatar użytkownika

Posty: 16
Lokalizacja: Warszawa
Sylwek napisał(a):
Wówczas 1 \le r \le j.


Czemu to jest oczywiste?
Góra
Mężczyzna Offline
PostNapisane: 14 maja 2018, o 20:53 
Użytkownik
Avatar użytkownika

Posty: 1428
Lokalizacja: Katowice
bo 1 + 2 + \ldots + j < k < 1 + 2 + \ldots + j + (j+1), więc liczba k jest pomiędzy liczbami 1 + 2 + \ldots + j i 1 + 2 + \ldots + j + (j+1), które różnią się o j+1
Góra
Mężczyzna Offline
PostNapisane: 23 maja 2018, o 13:07 
Moderator
Avatar użytkownika

Posty: 7716
Lokalizacja: Wrocław
timon92, Twoje rozwiązanie nie działa dla 13 \le 1 + 2 + 3 + 4 + 5.
Góra
Mężczyzna Offline
PostNapisane: 23 maja 2018, o 13:55 
Użytkownik
Avatar użytkownika

Posty: 1428
Lokalizacja: Katowice
Dasio11, słuszna uwaga, dzięki, psuje się nawet dla 5 \le 1+2+3

ogólniej, to nie zadziała, gdy n jest nieparzyste i 1+2+\ldots+(n-1)<k<1+2+\ldots+n
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 12 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 suma kątów w n-kącie (udowodnić przez indukcję)  m1h4u  5
 Dowod,liczba niewymierna  1894  4
 Ciekawa suma  mol_ksiazkowy  2
 Suma kwadratów kolejnych liczb naturalnych  kornishon  8
 udowodnij - suma wyrazow ciagu geometrycznego  Keendr  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl