Rješenja zadatka "1. ELMO zadatak 3" korisnika "matsimic"

Točno

26. kolovoza 2018. 10:20 (6 godine, 3 mjeseci)
Sakrij rješenje

Korisnik: matsimic
Zadatak: 1. ELMO zadatak 3 (Sakrij tekst zadatka)

Dokaži da je broj jedinica u svim neuređenim particijama nekog prirodnog broja jednak:

a) sumi brojeva različitih elemenata po svim particijama

b) sumi razlika, po svim particijama, najvećeg i drugog po veličini elementa

Neuređena particija prirodnog broja $n$ je multiskup prirodnih brojeva takav da je zbroj njegovih elemenata $n$ .

(Ivan Novak, Borna Šimić)

Upozorenje: Ovaj zadatak još niste riješili!
Kliknite ovdje kako biste prikazali rješenje.

Za prirodan broj $n$ , označimo s $P(n)$ broj neuređenih particija broja $n$ , te označimo s $D_n(k)$ broj particija broja $n$ koje sadrže barem $k$ jedinica. Uočimo da je broj particija koje sadrže točno $k$ jedinica tada jednak $D_n(k)-D_n(k+1).$

Promotrimo neku particiju broja $n$ koja sadrži barem $k$ jedinica. Uklanjanjem tih $k$ jedinica iz particije, generiramo particiju broja $n-k.$ Analogno, svakoj particiji broja $n-k$ možemo dodati $k$ jedinica i generirati particiju broja $n$ koja sadrži barem $k$ jedinica. Prema tome, između skupa particija broja $n$ s barem $k$ jedinica i skupa particija broja $n-k$ postoji bijekcija. Iz toga slijedi $D_n(k)=P(n-k)$

Prema tome, broj jedinica u svim particijama iznosi $(D_n(1)-D_n(2))+2(D_n(2)-D_n(3))+\ldots+n(D_n(n)-D_n(n+1))=$ $D_n(1)+D_n(2)+...+D_n(n)=$ $P(0)+P(1)+\ldots+P(n-1)$

Označimo s $H_n(k)$ broj particija broja $n$ u kojima se pojavljuje broj $k$ . Uočimo da je suma brojeva različitih elemenata po svim particijama jednaka $H_n(1)+H_n(2)+\ldots+H_n(n).$
Promotrimo particiju broja $n$ u kojoj se pojavljuje broj $k$ . Uklanjanjem broja $k$ generiramo particiju broja $n-k$ . Obratno, dodavanjem $k$ particiji broja $n-k$ generiramo particiju broja $n$ koja sadrži $k$ . Iz ovog zaključujemo da postoji bijekcija između skupa particija broja $n-k$ i skupa particija broja $n$ koje sadrže $k$ . Prema tome, imamo $H_n(k)=P(n-k)$ , iz čega slijedi $H_n(1)+H_n(2)+\ldots+H_n(n)=P(0)+P(1)+\ldots+P(n-1)$ što je i trebalo dokazati.

Prikažimo neuređene particije prirodnih brojeva dijagramom na sljedeći način: poredajmo brojeve unutar particije od najvećeg prema najmanjem i za svakog člana particije u vlastiti redak postavimo onoliko kvadratića koliko je on velik. Primijetimo sljedeću bijekciju na skupu particija: preslikamo cijeli dijagram preko pravca na kojem leži glavna dijagonala prvog kvadratića.

Ova bijekcija slika razliku najvećeg i drugog po veličini člana jedne particije u sve jedinice njoj pridružene particije, pa je time i suma svih razlika jednaka sumi broja jedinica po svim particijama, što je i trebalo pokazati.

a) Za prirodan broj $n$, označimo s $P(n)$ broj neuređenih particija broja $n$, te označimo s $D_n(k)$ broj particija broja $n$ koje sadrže barem $k$ jedinica. Uočimo da je broj particija koje sadrže točno $k$ jedinica tada jednak $D_n(k)-D_n(k+1).$\\ \\ Promotrimo neku particiju broja $n$ koja sadrži barem $k$ jedinica. Uklanjanjem tih $k$ jedinica iz particije, generiramo particiju broja $n-k.$ Analogno, svakoj particiji broja $n-k$ možemo dodati $k$ jedinica i generirati particiju broja $n$ koja sadrži barem $k$ jedinica. Prema tome, između skupa particija broja $n$ s barem $k$ jedinica i skupa particija broja $n-k$ postoji bijekcija. Iz toga slijedi $D_n(k)=P(n-k)$\\ \\ Prema tome, broj jedinica u svim particijama iznosi $$(D_n(1)-D_n(2))+2(D_n(2)-D_n(3))+\ldots+n(D_n(n)-D_n(n+1))=$$ $$D_n(1)+D_n(2)+...+D_n(n)=$$ $$P(0)+P(1)+\ldots+P(n-1)$$\\ \\ Označimo s $H_n(k)$ broj particija broja $n$ u kojima se pojavljuje broj $k$. Uočimo da je suma brojeva različitih elemenata po svim particijama jednaka $H_n(1)+H_n(2)+\ldots+H_n(n).$ \\ Promotrimo particiju broja $n$ u kojoj se pojavljuje broj $k$. Uklanjanjem broja $k$ generiramo particiju broja $n-k$. Obratno, dodavanjem $k$ particiji broja $n-k$ generiramo particiju broja $n$ koja sadrži $k$. Iz ovog zaključujemo da postoji bijekcija između skupa particija broja $n-k$ i skupa particija broja $n$ koje sadrže $k$. Prema tome, imamo $H_n(k)=P(n-k)$, iz čega slijedi $$H_n(1)+H_n(2)+\ldots+H_n(n)=P(0)+P(1)+\ldots+P(n-1)$$ što je i trebalo dokazati. b) Prikažimo neuređene particije prirodnih brojeva dijagramom na sljedeći način: poredajmo brojeve unutar particije od najvećeg prema najmanjem i za svakog člana particije u vlastiti redak postavimo onoliko kvadratića koliko je on velik. Primijetimo sljedeću bijekciju na skupu particija: preslikamo cijeli dijagram preko pravca na kojem leži glavna dijagonala prvog kvadratića. Ova bijekcija slika razliku najvećeg i drugog po veličini člana jedne particije u sve jedinice njoj pridružene particije, pa je time i suma svih razlika jednaka sumi broja jedinica po svim particijama, što je i trebalo pokazati.

Školjka

Ocjene: (1)