Złotówka jok: Na ile sposobów można rozmienić złotówkę?

jok: używając 1,2,5,10,20,50 groszówek

Yoyo: kawalarz

Basia: straszne zadanie; czy to matematyka dyskretna ?

Trivial: Trzeba wyprowadzić rekurencyjne zależności i policzyć.

Trivial: i tak, Basiek, to matematyka dyskretna.

Basia: wiem Trivial, ale to dość paskudne liczenie i myślę jakby to załatwić prościej niestety nic na "prościej" nie wymyśliłam

Trivial: Przepraszam, Basiu. Pomyliłem Cię z Baśkiem.

Trivial: Prościej raczej nie da rady.

Trivial: Tutaj jest zgrabnie wyjaśnione: http://wazniak.mimuw.edu.pl/index.php?title=Matematyka_dyskretna_1/Wyk%C5%82ad_7:_Funkcje_tworz%C4%85ce

matematyk: na w ch.. dużo sposobów

Basiek: Wtrącam się, witam Was− na przyszłość: przed godziną 12−tą to nie mogę być ja. Ale dzięki Trivial za odpowiedź.

Leszek: Na widzę to tak (zaczynajac od monet najdrobniejszych): Monetę 2gr można przedstawić na 2 sposoby: 2gr 2 * 1gr Zatem jakas tam funkcja: f(2gr)=2 Dalej mamy monetę 5gr.Możemy ją przedstawić w postaci: 5gr lub rozbijając ją najmniej drobnie na: 2*2gr + 1gr ale te 2gr też możemy przedstawić na f(2gr) sposoby więc:

	(2+f(2gr)−1)!		(2+1)!		6
f(5gr)=1+		=1+		=1+		=4
	2! (f(2gr)−1)!		2!*1!		2

Teraz moneta 10gr.Można ją przedstawić na takie sposoby: 10gr 2*5gr no i ponieważ każda moneta 5gr może oddzienie być rozmieniona tak że musi być co najmniej 1 moneta 1gr a moneta 10gr jest parzysta więc dochodzi jeszcze jedna możliwość którą pomineliśmy: 5*2gr (uwaga! tutaj juz nie rozdrabniamy monety 2gr bo wyjdzie możliwość uwzględniona wcześniej)

	(2+f(5gr)−1)!		(2+3)!		120
f(10gr)=2+		=2+		=2+		=12
	2! (f(5gr)−1)!		2!*3!		12

Dalej monata 20gr: 20gr 2*10gr

	(2+f(10gr)−1)!
f(20gr)=1+		=
	2! (f(10gr)−1)!

	(2+11)!		13!		12*13
1+		=1+		=1+		=1+78=79
	2!*11!		2!*11!		2

Moneta 50gr: 50gr 2*20gr+10gr Jednak pojawia sie problem: Jak połączyć rozdrabnianie jednocześnie monet 20gr i 10gr? Jak napisać wzór na kombinację z powtórzeniami w takim przypadku? Mimo to mam inne rowiazanie: 5*10gr(rozdrabniamy monety 10gr, nie używamy monet 20gr) dalej: jeśli są dwie monety 20gr to mamy 1 monetę 10gr (którą możemy rozdrobnić) 2*20gr + 10gr więc musimy dodać f(10gr) jeśli jest 1 moneta 20gr to mamy 3 monety 10gr 20gr + 3*10gr więc musimy dodać kombinacje 3 po f(10gr)

	(5+f(10gr)−1)!		(5+11)!
a=		=		=
	5! (f(10gr)−1)!		5!*11!

16!		12*13*14*15*16
	=		=4368
120*11!		120

	(3+f(10gr)−1)!		(3+11)!
b=		=		=
	3! (f(10gr)−1)!		3!*11!

14!		12*13*14
	=		=364
6*11!		6

Razem ilość możliwosci przybiera postać: f(50gr) = 1+a + b + f(10gr) = 1 + 4368 + 364 + 12 = 4745 No i ostatnia moneta 1zł: 1zł 2*50gr 5*20gr (czyli dodajemy 1 bo tylko jedna jest taka możliwość a nie została uwzględniona przy 2*50gr, podobnie jak z monetą 10gr)

	(2+f(50gr)−1)!		(2+4744)!
f(1zł)=2+		=2+		=
	2! (f(50gr)−1)!		2!*4744!

	4745*4746
2+		=11259887
	2

Pnieważ chdzi na o rozmienienie 1zł wiec opcja 1zł odpada i zostaje: 11259886 To jest mój ostateczny wynik. Niewiem czy dobrze ale niezdziwiłbym się jakby było źle...

panteon: coś mi nie gra do 10gr jest ok ale 20gr można przedstawić tylko jako 2*10gr lub 1*20gr więc powinno być 12*12 +1=25 chyba, że czegoś nie rozumiem?

Leszek: Źle liczysz. Musisz policzyć każda kombinacja z jednej monety razy każda przez z drugiej z tym ze pomijamy te które się powtarzają ale mają inną kolejność(bo kolejność nie ma znaczenia). Trzeba liczyć kombinacje z powtórzeniami.

panteon: już sam do tego doszedłem i zgadza mi się (przynajmniej do 20gr bo potem się już gubie i mi się nie chce liczyć dalej)

hyhy: 293 .

Godzio: Można zrobić to ze splotu funkcji z tego co pamiętam, a w tym wypadku ciągu

Godzio: Przedstawię zarys tego, gdyby kogoś zainteresowało Szukamy rozwiązań całkowitych nieujemnych równania: x₁ + 2x₂ + 5x₃ + 10x₄ + 20x₅ + 50x₆ = 100 a_n − liczba rozwiązań równania x₁ = n ⇒ a_n = 1,

	⎧	1, n = 2k
bn − liczba rozwiązań równania 2x2 = n ⇒ bn =	⎩	0, n ≠ 2k

Splot b_n' = (a*b)_n jest liczbą rozwiązań równania: x₁ + 2x₂ = n

	n
bn' = ∑k=0nbkan−k=∑k=0nbk=b0+b2+...+b2[n/2] = [		] + 1
	2

	⎧	1, n = 5k
Dalej, cn − liczba rozwiązań równania 5x3 = n ⇒ cn =	⎩	0, n ≠ 5k

Podobnie splot c_n' = (b'*c)_n = ∑_k=0ⁿb_k'c_n−k = (x) ∑_k=0¹⁰⁰b_k'c_n−k = b₀' + b₅' + b₁₀' + ... + b₁₀₀' = = 1 + 3 + 6 + 8 + 11 + 13 + 16 + 18 + ... itd. trzeba zsumować

	⎧	1, k = 10k
dn − liczba rozwiązań równania 10x4 = n ⇒ dn =	⎩	0, k ≠ 10k

	⎧	1, k = 20k
en − liczba rozwiązań równania 20x5 = n ⇒ en =	⎩	0, k ≠ 20k

	⎧	1, k = 50k
fn − liczba rozwiązań równania 50x6 = n ⇒ fn =	⎩	0, k ≠ 50k

I tworzymy sploty: d_n' = (c'*d)_n = ∑_k=0ⁿc'_kd_n−k e_n' = (d'*e)_n = ∑_k=0ⁿd'_ke_n−k = f_n' = (e'*f)_n = ∑_k=0¹⁰⁰e'_kf_100−k − liczba rozwiązań naszego równania, ∑_k=0¹⁰⁰e'_kf_100−k = e₁₀₀'f₀ + e₅₀'f₅₀ + e₀'f₁₀₀ = = e₀' + e₅₀' + e₁₀₀ '

lkoikm: Firma Nokia Solutions and Networks zorganizowała konkurs z podobnym (nieco trudniejszym) zadaniem: Na ile sposobów można rozmienić banknot 1024 N$N na nominały o mniejszej wartości należące do zbioru {2i} N$N, gdzie i = 0,1,2,…,9? więcej info na: http://bepartofsomething.eu/ powodzenia

GK: Poprawna odpowiedź to 3776. Obliczone programowo.