99 groszy reszty

[cardemon]

Zagadka, której moim zdaniem nie da się rozwiązać bez pomocy komputera. Oto
jej treść:

Poszedłem do sklepu mając dokładnie jedną złotówkę w kieszeni. Kupiłem sobie
jednego cukierka za jeden grosz. Pytanie brzmi: na ile możliwych sposobów
sprzedawca mógł mi wydać reszty zakładając, że miał dowolne ilości jedno-,
dwu-, pięcio-, dziesięcio-, dwudziesto- i pięćdziesięciogroszówek?

CdM

[Gość: grzesiek]

4366.

[cardemon]

Gość portalu: grzesiek napisał(a):

> 4366


Super!!! Moje gratulacje!
A czym możesz nam, forumowiczom, zdradzić, jak doszedłeś do tej liczby?

Pozdrawiam, CdM

[Gość: grzesiek]

Komputer mi obliczyl. Po pierwszych próbach liczenia na piechotę szybko
zgodzilem się z sugestią Autora że bez komputera to niemożliwe.
Program, jeśli się użyje rekurencji, jest bardzo prosty.

[Gość: pam75]

adanie jest nieprecyzyjnie sformułowane. Coo znaczy "na ile sposobów"
Jeżeli "sposobem" jest zestaw monet w reszcie, to tych zestawów nie jest tak
wiele Najmniejszy zawiera 6 monet(50,20,20,5,2,2) a największy 99 monet(po 1
groszu), czyli takich reszt jest nie więcej niż 94. Jeżeli rozróżniamy
kolejność otrzymywanych monet, to przy 97 monetach(95 jednogroszówek i 2
dwugroszówek) można rozmieścic obok groszy na 97*96/2=4456 sposobów. Przy 93
jednogroszówkach i 3 dwugroszówkach jest 96*95*94/6 = 142880 reszt, a więc
aprobata rozwiązania wyżej jest dla mnie niezrozumiała.

[Gość: slawek]

Przepraszam za zlosliwosc, ale mniej wiecej polowa z tego co napisale(a)s jest
prawda.
Jako wskazowke podam, ze kwote 10gr mozna przedstawic na 11 sposobow.

pozdrawiam,
slawek

[Gość: pam75]

W związku z wpisem sławka(wyżej)
10,55, 5221,52111, 511111,22111111,211111111,1111111111,2221111,222211,
22222 - przy zmianach kolejności - 128 możliwości.
Rzeczywiście, przeoczyłem fakt,że np 50 monet może zawierać 1 50-groszówkę i 49
jednogroszówek jak również 50 2-groszówek.Nie zmienia to faktu,ze prezentowane
rozwiązanie jest przesadnie duże - w przypadku róznych zestawów monet w
reszcie, albo przesadnie mało, przy uwzględnianiu kolejności monet.
Złośliwość była nie taka wielka, a uatrakcyjnia wpis. Dzięki za uwagę, bo
branąłbym w przekonanie o słuszności użytej przeze mnie metody.

[marchewa4]

Gość portalu: pam75 napisał(a):

> Rzeczywiście, przeoczyłem fakt,że np 50 monet może zawierać 1 50-groszówkę i
> 49jednogroszówek jak również 50 2-groszówek. Nie zmienia to faktu,ze
> prezentowane rozwiązanie jest przesadnie duże - w przypadku róznych zestawów
> monet w reszcie

Lepiej byloby napisac "wydaje mi sie przesadnie duze". podane rozwiazanie nie
jest przesadnie duze - jest poprawne.

Rozwaz kwote 15 gr. Zgodnie z Twoim rozumowanie minimalna liczba monet, ktore
realituja te kwote wynosi 2 (10 gr i 5 gr), maksymalna 15 a zatem istnieje 14
roznych mozliwosci. Nieprawda, istnieja 22 mozliwosci:

10gr 5gr 2gr 1gr
1 1 00 00 (02 monety)
1 0 02 01 (04 monety)
1 0 01 03 (05 monet)
1 0 00 05 (06 monet)
0 3 00 00 (03 monety)
0 2 02 01 (05 monet)
0 2 01 03 (06 monet)
0 2 00 05 (07 monet)
0 1 05 00 (06 monet)
0 1 04 02 (07 monet)
0 1 03 04 (08 monet)
0 1 02 06 (09 monet)
0 1 01 08 (10 monet)
0 1 00 10 (11 monet)
0 0 07 01 (08 monet)
0 0 06 03 (09 monet)
0 0 05 05 (10 monet)
0 0 04 07 (11 monet)
0 0 03 09 (12 monet)
0 0 02 11 (13 monet)
0 0 01 13 (14 monet)
0 0 00 15 (15 monet)

Pozdrowienia
M.

[marchewa4]

Gość portalu: pam75 napisał(a):

> adanie jest nieprecyzyjnie sformułowane. Coo znaczy "na ile sposobów"
"Na ile sposobow" oznacza ile jest takich <B>roznych<\B> zbiorow monet, ktore w
sumie daja 99 gr. Nie zalezy to oczywiscie od kolejnosci.
Rowna liczba monet w dwoch zestawach nie oznacza, ze zestawy sa rowne, jeslii
uzyte monety sa inne.
Pojednyczy sposob mozesz sobue wyobrazic jako szostke liczb x50, x20, x10, x5,
x2, x1 gdzie kazde xi oznacza liczbe uzytych monet i-groszowych.

Pozdrowienia
M.

[marchewa4]

cardemon napisał:

> Zagadka, której moim zdaniem nie da się rozwiązać bez pomocy komputera.

Rozumiem, ze to zdanie bylo sugestia pokazania metody wyznaczenie szukanej
liczby bez uzycia komputera, a zatem...


Na potrzeby rozwiazania podzielmy monety na grube (50,20,10) i drobne (5,2,1).
Zauwazmy, ze zbior wszystkich mozliwych realizacji kwoty 99 mozemy podzielic na
rozlaczne podzbiory, w ktorych monetami grubymi realizujemy kolejno kwoty 90,
80, ..., 10, 0 zas drobnymi odpowiednio 9, 19, .., 89, 99.
Rozlacznosc tych podzbiorow nie wymaga chyba dowodu, a to, ze ich suma stanowi
zbior wszystkich mozliwych realizacji kwoty 99 jest oczywiste.
Szukana przez nas liczba stanowi zatem sume licznosci wszystkich tych
podzbiorow.
Rozwazmy przykladowo jeden z nich: G(80) D(19)
Jego licznosc stanowi iloczyn licznosci dwoch zbiorow: relizacji kwoty 80 za
pomoca monet grubych i realizacji kwoty 19 za pomoca monet drobnych.
Analogicznie jest dla pozostalych podzbiorow.
Nietrudno wyznaczyc recznie licznosci zbiorow G(10x) (wartosci ponizej).

Pozostaje wyznaczyc licznosci zbiorow D(10x-1).

Zauwazmy, ze mamy 3 monety, ale tylko dwa stopnie swobody tzn. jesli okreslimy
liczbe piatek i dwojek, to liczba jedynek nie moze byc juz dowolna, ale musi
dopelniac realizowana przez nas kwote.
Dla liczby 10x-1 mozemy uzyc od 0 do 2x-1 monet pieciogroszowych.
Co wiecej, dla liczby 10x-1 i p monet pieciogroszowych (0 <= p <= 2x-1) mozemy
uzyc od 0 do [(10x-1-5p)/2] monet dwugroszowych, gdzie [m] oznacza czesc
calkowita liczby m.

Szukana licznosc zbioru D(10x-1) wynosi zatem
L(D(10x-1)) =
suma{po p od 0 do 2x-1} ([(10x-1-5p)/2]+1) =
{rozbijamy na p parzyste i nieparzyste}
suma{po j od 0 do x-1} ([(10x-1-10j)/2]+1) + suma{po j od 0 do x-1} ([(10x-1-
10j-5)/2]+1) =
suma{po j od 0 do x-1} (5x-5j-1+1) + suma{po j od 0 do x-1} (5x-5j-3+1) =
suma{po j od 0 do x-1} (5x-5j) + suma{po j od 0 do x-1} (5x-5j-2) =
suma{po j od 0 do x-1} (10x-10j-2) =
10 suma{po j od 0 do x-1} (x) - 10 suma{po j od 0 do x-1} (j) - 2 suma{po j od
0 do x-1} (1)=
10x^2 -5x(x-1) -2x =
5x^2+3x

Ostatecznie wyznaczamy licznosci poszczegolnych zbiorow:

x L(G(100-10x)) L(D(10x-1)) = 5x^2+3x
01 G(90) 8 D(09) 008
02 G(80) 7 D(19) 026
03 G(70) 6 D(29) 054
04 G(60) 5 D(39) 092
05 G(50) 4 D(49) 140
06 G(40) 3 D(59) 198
07 G(30) 2 D(69) 266
08 G(20) 2 D(79) 344
09 G(10) 1 D(89) 432
10 G(0) 1 D(99) 530

Teraz wystarczy parami wymnozyc, wszystko zsumowac i uzyskujemy liczbe 4366


Pozdrowienia

M.

[Gość: pam75]

Jestem pod wrazeniem. Też wreszcie doszedłem do prawidłowego wyniku inną nieco
metodą - realizacja reszty przy użycu róznych podzbiorów monet ze zbioru
{1,2,5,10,20, 50} z tym,że kazda moneta wybranego podzbioru powinna wystapić
conajmniej jeeden raz. Podzbiory zawierajęce tylko monety"parzyste" można było
odrzucić i w końcu zadanie okazało sie nie takie trudne, nawet "na piechotkę".
Wniosek: Pierwsze pomysły traktuj podejrzliwie - to mogą być złudzenia.
Anonimowość tutejszych wpisów łatwiej pozwala przeżyć kompromitacje
Dziękuję i pozdrawiam.

[cardemon]

Gość portalu: pam75 napisał(a):

> Jestem pod wrazeniem. (...)

Też jestem pod wrażeniem! Zagadnienie po raz pierwszy sformułował matematyk
George Polya prawie pół wieku temu. I na pewno nie miał pod ręką kompa, by to
wszystko na nim policzyć. Wszystkim, którzy zabrali się za to zadanie i
prawidłowo doszli do liczby 4366, gratuluję!

Pozdrawiam, CdM

[sojuz1]

cardemon napisał:

> Zagadka, której moim zdaniem nie da się rozwiązać bez pomocy komputera. Oto
> jej treść:
>
> Poszedłem do sklepu mając dokładnie jedną złotówkę w kieszeni. Kupiłem sobie
> jednego cukierka za jeden grosz.
Gdzieś ty go kupił?

>Pytanie brzmi: na ile możliwych sposobów
> sprzedawca mógł mi wydać reszty zakładając, że miał dowolne ilości jedno-,
> dwu-, pięcio-, dziesięcio-, dwudziesto- i pięćdziesięciogroszówek?
Skoro miał dowolne ilości to logiczne, że ma nieskończoną liczbę sposobów.

[Gość: dekornel 1]

Sojuz wkorzystal brak precyzji w sformułowaniu zadania i kombinuje tak:
Jesli jest nieskończenie wiele jednogroszówek do wydania, to wydajac tylko
jeden grosz można wziąc jednogrszówkę na nieskończona liczbę sposobów.
Sformułowanie powinno brzmieć:`1) Ile jest róznych zestawów monet dających w
sumie 99gr.(Wydający nie musi ich mieć nieskończenie wiele wystarczy 171 monet:
1-50gr;4 -20,9 -10;19 -5;49 -2 i99 -1gr)

[wkniaziuk]

A moim zdaniem da się. Pa!