MATEMANIJA

Ponuđeni su brojevi od [inlmath]1,2,3,\ldots,10[/inlmath]. Trebamo od tih brojeva da izaberemo [inlmath]3[/inlmath] broja čiji je zbir (bez ponovljenih brojeva):
a) jednak [inlmath]9[/inlmath]
b) manji od [inlmath]9[/inlmath]

a) Jasno je da su to zbirovi [inlmath]6+2+1=9;\;5+3+1=9;\;4+3+2=9;[/inlmath] . Međutim, mene interesuje da li postoji neka posebna metoda ili formula za rešavanje ovakvih problema? Moram li da razbijam brojeve po slučajevima, što može potrajati poprilično, jer šta bi bilo na primer kada bih morao da biram [inlmath]3[/inlmath] broja čiji je zbir, npr [inlmath]388[/inlmath].

b) Isto mi pada na pamet da rešim ovaj zadatak samo po slučajevima, gde ću pre toga eliminisati brojeve [inlmath]10,9,8,7,6[/inlmath].

Nisam siguran kako da ti odgovorim na pitanje. Moram da pitam odakle je ovaj zadatak, da li je sigurno vezan za teoriju brojeva ili je možda iz kombinatorike, i da li si ti ovo smislio kao primer ili je iz neke zbirke (buni me broj [inlmath]10[/inlmath] koji je ovde suvišan)?
Ono što mogu da ti kažem je da ne postoji nikakva konkretna formula koja bi se mogla primeniti u ovom zadatku. Meni se čini da se ovde možeš služiti samo čistom logikom, kao što si i ti učinio.
Kažem, pomoglo bi ako bi napisao odakle je zadatak i gde se ti susrećeš sa istim (fakultet, srednja škola...).

Zapravo, moze se i malo vise reci. Naime, broj particija broja [inlmath]n[/inlmath] na zbir tacno [inlmath]k[/inlmath] razlicitih brojeva je jednak koeficijentu koji stoji uz [inlmath]x^n[/inlmath] u razvoju funkcije [inlmath]\displaystyle\frac{x^{k+{\large k\choose2}}}{\prod_{j=1}^k(1-x^j)}[/inlmath] u okolini nule (u sustini tamo gde postoji razvoj). Na primer ovde bismo imali [inlmath]\displaystyle f(x)=\frac{x^6}{(1-x)(1-x^2)(1-x^3)}[/inlmath] i vazi (ako ne zelite da pisete formalno velikog O, onda stavite tri tacke posle plusa) [inlmath]f(x)=x^6+x^7+2x^8+3x^9+4x^{10}+O(x^{11})[/inlmath], kad [inlmath]x\to0[/inlmath] [znam, nema potrebe ovoliko razvijati, moze se skratiti]. Odatle i vidimo da je resenje dela pod a) jednako [inlmath]3[/inlmath], a vide se i resenja za deo pod b).

Naravno, lakse je bilo peske sve uraditi, no pitao si za opstu situaciju.

Inace, sam zadatak mi je malo cudno formulisan. Iz tvoje postavke sam pre shvatio da je dovoljno samo naci primer od tri broja tako da vaze delovi a) ili b), no pretpostavljam da si pre hteo da pitas koliko ima takvih primera (kombinacija).

Zadatak je iz knjige Analiza algebrom ili iz knjige Kombinatorika, iz Matematičke gimnazije. Nisam duže vreme kući, tako da ne mogu biti siguran iz koje od te dve.

Inače, saznao sam da je to problem pod imenom "Suma svih podskupova" https://en.wikipedia.org/wiki/Subset_sum_problem

@Onomatopeja Odakle vam ova formula? Jel su ovo funkcije generatrise (o kojima nemam pojma ) ?
Jel rešenje pod [inlmath]b:[/inlmath] [inlmath]\ 4[/inlmath] (koeficijenti koji stoje uz [inlmath]x^8[/inlmath], [inlmath]x^7[/inlmath] i [inlmath]x^6[/inlmath])? Generalno, zanima me do koliko brojeva ova metoda može da funkcioniše dok ne postane previše kompleksna za računanje, šta bi bilo da je umesto [inlmath]9[/inlmath] broj [inlmath]7284[/inlmath]?

Tako je, povezano je sa funkcijama generatrisama. Za nesto detaljnije, potrazi na netu o funkcijama [inlmath]p(n,k)[/inlmath] (number of partitions of [inlmath]n[/inlmath] with [inlmath]k[/inlmath] parts) i [inlmath]q(n,k)[/inlmath] (number of partitions of [inlmath]n[/inlmath] with [inlmath]k[/inlmath] distinct parts). To su poznate funkcije.

Svakako bi bilo dosta slozenije da smo imali [inlmath]7284[/inlmath] (no ne znam zasto bismo i ocekivali da tu imamo relativno jednostavan slucaj).