Matematyka.pl

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ń

Niech będzie dane \(\displaystyle{ n}\). Udowodnić, że każde \(\displaystyle{ k}\), takie że \(\displaystyle{ 1 \le k \le 1 + 2 + ... + n}\) można przedstawić jako sumę wybranych liczb ze zbioru \(\displaystyle{ \left\{ 1, 2, 3, ..., n \right\}}\), przy czym wykorzystując każdy element maksymalnie raz.

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

Teraz wystarczy odnotować, że dla \(\displaystyle{ 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ę \(\displaystyle{ 1+2+\ldots+n}\).
Jest to oczywiście przedstawienie liczby \(\displaystyle{ 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
\(\displaystyle{ (1+2+\ldots+n)-k}\), gdzie \(\displaystyle{ k}\) przebiega zbiór \(\displaystyle{ \left\{ 1,2, \ldots n\right\}}\), dokładnie dwie liczby, aby uzyskać reprezentację w pożądanej przez nas postaci którejś z liczb
\(\displaystyle{ (1+2+\ldots+n)-(1+2), \ldots (1+2+\ldots+n)-(n+n-1)}\) i ogólniej dokładnie \(\displaystyle{ \eta}\) liczb, \(\displaystyle{ \ \eta \in \left\{ 1, 2, \dots n-1\right\}}\) otrzymując w ten sposób dowolną spośród liczb
\(\displaystyle{ (1+2+\ldots+n)-(1+2+\ldots+\eta), \ldots (1+2+\ldots+n)- ((n-\eta+1)+\ldots+n)}\) (malejąco).
Pozostaje zauważyć, że
\(\displaystyle{ (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 \(\displaystyle{ \eta\in \left\{ 1,2, \ldots n-1\right\}}\).

To jest sprytniejsze, niźli poprzednie podejście, ale pewnie jakoś nieścisłe.

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!

A może tak zapisać - liczby postaci \(\displaystyle{ k = 1 + 2 + ... + j}\) mają trywialne przedstawienie w postaci szukanej sumy.

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

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

Wówczas \(\displaystyle{ 1 \le r \le j}\).

Zatem \(\displaystyle{ k=1 + 2 + ... + j + (j+1) - r}\), czyli wśród liczb \(\displaystyle{ \lbrace 1, 2, ..., j, j+1 \rbrace}\) pomijamy jedynie jedną liczbę \(\displaystyle{ r}\) i mamy poszukiwane przedstawienie.

O! To jest właśnie różnica między sztuką a rzemiosłem, widać ją nawet w tak prostym zadaniu.

Inspirowane Twoim drugim sposobem

A przecież indukcyjnie idzie tak prosto:
Dla \(\displaystyle{ n=2}\) sprawdzamy na palcach.
Załóżmy, że każda liczba od \(\displaystyle{ 1}\) do \(\displaystyle{ 1+\dots+n}\) ma szukane przedstawienia.
Weźmy dowolną liczbę nie większą od \(\displaystyle{ 1+\dots+n+(n+1)}\). Jeżeli jest mniejsza lub równa niż \(\displaystyle{ 1+\dots+n}\) to przedstawienie istnieje na mocy założenia. A jeżeli jest większa, to jest postaci \(\displaystyle{ (n+1)+k}\), gdzie \(\displaystyle{ k}\) jest nie większe niż \(\displaystyle{ 1+\dots+n}\) wiec ...

dzielimy \(\displaystyle{ k}\) z resztą przez \(\displaystyle{ n+1}\) i otrzymujemy \(\displaystyle{ k=a\cdot(n+1)+r}\) przy czym \(\displaystyle{ 0\le r \le n}\) oraz \(\displaystyle{ a\le \frac n2}\) (gdyż \(\displaystyle{ k \le 1+2+\ldots+n = \frac n2 (n+1)}\))

wobec tego

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

i każdą z \(\displaystyle{ a}\) liczb \(\displaystyle{ n+1}\) zapisujemy w postaci \(\displaystyle{ j+(n+1-j)}\) dla parami różnych \(\displaystyle{ j}\) dbając o to, by \(\displaystyle{ j \neq r \neq n+1-j}\) (co da się zrobić ze względu na szacowanie \(\displaystyle{ a\le \frac n2}\))

Sylwek pisze: Wówczas \(\displaystyle{ 1 \le r \le j}\).

Czemu to jest oczywiste?

bo \(\displaystyle{ 1 + 2 + \ldots + j < k < 1 + 2 + \ldots + j + (j+1)}\), więc liczba \(\displaystyle{ k}\) jest pomiędzy liczbami \(\displaystyle{ 1 + 2 + \ldots + j}\) i \(\displaystyle{ 1 + 2 + \ldots + j + (j+1)}\), które różnią się o \(\displaystyle{ j+1}\)

timon92, Twoje rozwiązanie nie działa dla \(\displaystyle{ 13 \le 1 + 2 + 3 + 4 + 5.}\)

Dasio11, słuszna uwaga, dzięki, psuje się nawet dla \(\displaystyle{ 5 \le 1+2+3}\)

ogólniej, to nie zadziała, gdy \(\displaystyle{ n}\) jest nieparzyste i \(\displaystyle{ 1+2+\ldots+(n-1)<k<1+2+\ldots+n}\)