Начини за получаване на определена сума

[martixy]

Попаднах на една интересна задачка-закачка, която обаче се оказа над възможностите ми:
Колко начина има да съберем 2 лева на стотинки?
Всякаква помощ е добре дошла.

[Гост]

Сегашните стотинки са със стойности 5, 10, 20, 50, 100 (1 лев).
Нека имаме [tex]a_i[/tex] от всяка, значи търсим броя на неотрицателните целочислени решения на уравнението
[tex]5a_1 +10a_2+20a_3+50a_4+100a_5=2000\Leftrightarrow a_1+2a_2+4a_3+10a_4+20a_5=400\Rightarrow 2|a_1,a_1=2b_1, b_1\ge 0[/tex]
[tex]b_1+a_2+2a_3+5a_4+10a_5=20[/tex]
Оттук [tex]a_5\le 2[/tex]
Сега трябва да се разглеждат [tex]3[/tex] случая.
1) [tex]a_5=2\Rightarrow b_1+a_2+2a_3+5a_4=0\Rightarrow (0,0,0,0,2)[/tex]
2) [tex]a_5=1\rightarrow b_1+a_2+2a_3+5a_4=10 \Rightarrow a_4\le2[/tex]
2.1) [tex]a_4=2\Rightarrow (0,0,0,2,1)[/tex]
2.2) [tex]a_4=1\Rightarrow b_1+a_2+2a_3=5\Rightarrow a_3\le 2[/tex]
2.2.1) [tex]a_3=2\Rightarrow b_1+a_2=1\Rightarrow (0,1,2,1,1), (2,1,2,1,1)[/tex]
2.2.2) [tex]a_3=1\Rightarrow b_1+a_2=3\Rightarrow (0,3,1,1,1), (2,2,1,1,1), (4,1,1,1,1), (6,0,1,1,1)[/tex]
и тн