Nowy system monetarny.

[Gość: antyp]

Ty jako władca (w przypadku Pań – władczyni) państwa , wydałeś (aś) edykt, w
którym zostało postanowione, że każda kwota pieniędzy do 100 złotych
(włącznie), musi być odliczona za pomocą co najwyżej dwóch monet (być może o
takiej samej wartości). Monety o jakich nominałach musi wybić Twoja mennica?
Pamiętaj przy tym, że twój nadworny grawer, który robi projekty monet, to
zdzierca wprost skandaliczny, (ale ściąć go nie możesz, bo nie masz innego),
dlatego musisz maksymalnie ograniczyć ilość monet o różnych nominałach.

18 monet

[stomek]

Na razie mam 18 monet, ale podejrzewam, że to nie jest
granica możliwości.
Niech ktoś poda lepszy wyniki to zacznę się dalej
zastanawiać.

Tomek

[Gość: Marcin Miga]

Ciekawe zadanie...
Być może to:
www27.brinkster.com/marcinm/zip/sprnom.zip
pomoże w sprawdzaniu, czy już wszystkie możliwości zostały
wykorzystane...

pozdrawiaMM
PS. Witam, bo to mój pierwszy post tu.

[cardemon]

Programik Marcina bardzo zgrabny, moje gratulacje! :)

Natomiast co do odpowiedzi, to zgadzam się z rozwiązaniem Tomka. System
dziesiętny jest chyba najlepszą podpowiedzią na znalezienie optymalnego
rozwiązania. Wystarczy więc wziąć liczby od 1 do 9 oraz od 10 do 90 (są jeszcze
dwa inne równoważne zbiory), by przez sumę dowolnych dwóch lub za pomocą jednej
z nich otrzymać dowolną liczbę od 1 do 100. W sumie trzeba więc 18 różnych
monet.

pzdr. CdM

Nowy system monetarny.

[Gość: antyp]

Znam rozwiązanie tej zagadki z mniejszą od 18 ilością monet.

[cardemon]

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

> Znam rozwiązanie tej zagadki z mniejszą od 18 ilością monet.

Ha! To zmienia całkowicie postać rzeczy. Teraz warto nad tym pogłówkować.
Przede wszystkim widać, że monet musi być więcej niż 13 bowiem nierówność:

x + x!/[2!*(x-2)!] >= 100

jest prawdziwa dla x>=14. Dla x=14 i x=15 ilość możliwych kombinacji wynosi
odpowiednio 105 i 120, a ponieważ niektóre sumy się siłą rzeczy powtarzają
(choćby już przy przedstawieniu liczb pierwszej dziesiątki), to i zapewne
niemożliwe jest wykonanie powyższego zadania za pomocą zbiorów 14 czy 15 monet.
Poszukiwany jest więc najprawdopodobniej zbiór siedemnastu monet. Tyle
przemyśleń na gorąco.

pzdr. CdM

PS. Mam nadzieję, że w rozwiązaniu nie ma żadnego "podstępu" (np. w korzystaniu
z połówek monet).

[cardemon]

cardemon napisał:

> x + x!/[2!*(x-2)!] >= 100

Właśnie się złapałem na tym, że ten wzór powinien raczej brzmieć:

2x + x!/[2!*(x-2)!] >= 100

(...)

[cardemon]

Im bardziej wgłębiam się w tę zagadkę, tym bardziej staje się ona dla mnie
intrygująca. I choć nadal nie znalazłem do niej rozwiązania, to wierzę w to, że
wcześniej czy później musi ono paść! :)

Przede wszystkim chyba zabrnąłem w ciemny zaułek. Udało mi się dojść "wysiłkiem
umysłu" do rozwiązania, w którym za pomocą 17 różnych monet otrzymuję 99(!)
róznych sum (zabrakło mi liczby 31) i na tym koniec. Oto te nominały:
1,2,3,4,5,10,16,17,18,19,20,37 (może być też 38),43,48,69,75,80.
Moim kolejnym krokiem było więc rozważenie, czy by nie zaprzęgnąć do pracy
komputera, niech on sobie liczy, a ja będę się słodko lenił. :)

Wstępne oszacowania nie dają jednak powodu do optymizmu:

1) Przeliczenie "na głupa" wszystkich możliwości - 6.65*10^18 kombinacji;
2) Wiadomo przecież jednak, że jedynka musi być jedną z tych 17-stu liczb, to
obniża ilość kombinacji do 1.35*10^18;
3) No dobrze, ale przecież równie dobrze wiadomo, że trzeba wybrać przynajmniej
cztery liczby pierwszej dziesiątki. To zmniejsza ilość kombinacji do 1.64*10^15;
4) A gdyby wziąć wszystkie liczby pierwszej dziesiątki, to ilość kombinacji dla
pozostałej siódemki liczb ograniczyłaby się do 7.47*10^9 - ciągle zbyt dużo!

Widać więc, że bez sprytnego algorytmu się nie obędzie. A może ktoś ma lepszy
pomysł?

[Gość: Uller]

Hej. Jestem tu nowy.
Po ciezkich bojach znalazłem rozwiązanie z 17 cyframi.
1, 3, 5, 7, 9, 11, 13, 15, 16, 33, 34, 51, 52, 69, 70, 87, 88

[Gość: pafcio]

brawo

Nowy system monetarny.

[Gość: antyp]

Znam rozwiązanie tej zagadki z mniejszą od 17 ilością monet

Ludzie - ruszcie głowami!

[stomek]

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

> Znam rozwiązanie tej zagadki z mniejszą od 17 ilością monet

Z 16 monetami dochodzę do 96 i dalej ściana.
Może ktoś to wreszcie rozwiąże?

Tomek

[Gość: ALP]

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

> Hej. Jestem tu nowy.
> Po ciezkich bojach znalazłem rozwiązanie z 17 cyframi.
> 1, 3, 5, 7, 9, 11, 13, 15, 16, 33, 34, 51, 52, 69, 70, 87, 88

Jak w takim rozwiazaniu uzyskac 3PLN z 2 monet ? Chyba sie nie da. Albo trzeba
zmienic tresc albo dochodza jeszce 2 monety 2PLN i dla czepialskich 0PLn(aby
uzyskac 1PLN jako sume 2 monet :)

[Gość: ALP]

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

> Gość portalu: Uller napisał(a):
>
> > Hej. Jestem tu nowy.
> > Po ciezkich bojach znalazłem rozwiązanie z 17 cyframi.
> > 1, 3, 5, 7, 9, 11, 13, 15, 16, 33, 34, 51, 52, 69, 70, 87, 88
>
> Jak w takim rozwiazaniu uzyskac 3PLN z 2 monet ? Chyba sie nie da. Albo
trzeba
> zmienic tresc albo dochodza jeszce 2 monety 2PLN i dla czepialskich 0PLn(aby
> uzyskac 1PLN jako sume 2 monet :)

Dobra zle przeczytalem - "conajwyzej 2 monet" :)

Nowy system monetarny - podpowiedź

[Gość: Antyp]

Moneta o wartości 50 jest największym nominałem, który należy wybić w Twojej
mennicy. Nie jestem pewny czy ta podpowiedź bardzo ułatwi znalezienie
optymalnego rozwiązania. Ale ja po przyjęciu takiego założenia znalazłem
rozwiązanie tej główkołamki z mniej niż 17 różnymi monetami.

[Gość: ALP]

Uzywaja 16 monet uzyskuje 96 ze 100 monet - brakuje mi 31;32;74 i 79. Hmm
trzeba jeszzce troszke pokombinowac :)

[Gość: ALP]

Dobra ja sie poddaje:) Ta zagadka juz mi spac nie daje i w glowie mi sie kreci
od liczb :) Poprosze rozwiazanie jezeli mozna ?:)Proponuje na forum a jezeli
ktos sie z nia jeszcze meczy ;) to na priva [e-mail]

Nowy system monetarny - podpowiedź 2

[Gość: Antyp]

W moim rozwiązaniu idzie to tak 1,3,......,47,49,50.

[Gość: ALP]

3 sposrod liczb, ktore podales musialy sie w rozwiazaniu znalezc wiec za duzo
nie podpowiedziales :)

pozdr.
ALP

[uller]

Ja tam się nie poddaje. Jeno nie mam zbyt wiele czasu, ale jeżeli do weekendu
nie padnie odpowiedz to popracuję nad tym ciekawym zadankiem.

Jest 16!!!!!!!!!!!

[stomek]

1 3 4 9 11 16 20 25 30 34 39 41 46 47 49 50

Problem padł po użyciu podpowiedzi, komputera i głowy:
1) głowa wymyśliła jak zredukować problem i napisała programiki szukające
częściowych rozwiązań w różnych wariantach z wykorzystaniem podpowiedzi
2) komputer poszukał cześciowych rozwiązań
3) głowa przeanalizowała częściowe rozwiązania, sprowadziła problem do
sprawdzenia 144456 możliwości i napisała programik
4) komputer sprawdził i ZNALAZŁ!

Jaki cud, że po drodze nie było wrednych bug'ów. Programiki były na tyle
zmyślne, że w sumie działały tylko kilka minut.
Nie mam energii sprawdzać, czy ta metoda powiodłaby się bez podpowiedzi. Na
pewno udałoby się nie korzystając z podpowiedzi 2, ale nie wiem jak by to było
bez podpowiedzi 1 - chyba krucho.

Antyp, napisz jak ty doszedłeś to tego rozwiązania! Ja mordowałem się długo i
bez rezultatu przy użyciu kartki i ołówka. Dopiero wykorzystanie komputera dało
efekt.

pozdrawiam,
Tomek

Szczerze gratuluję

[Gość: Antyp]

No niezła ta głowa. Mój sposób rozwiązania tego problemu, był praktycznie
identyczny z twoim. Też w końcowej fazie użyłem programu komputerowego.
Liczby monet raczej nie da się zmniejszyć. Rozwiązanie jest identyczne z moim,
co utwierdza mnie w przekonaniu, że jest tylko jedna możliwość. Jeszcze raz Ci
gratuluję.

[stomek]

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

> No niezła ta głowa. Mój sposób rozwiązania tego problemu, był praktycznie
> identyczny z twoim. Też w końcowej fazie użyłem programu komputerowego.

Ale jak wpadłeś na to aby największą monetą było 50? Tak po prostu to założyłeś,
żeby sprawdzić czy wyjdzie wynik czy jakoś to wydedukowałeś?

Chętnie wymienię się z Tobą szczegółami pomysłu.

Ja napisałem dwa programiki szukające częściowych rozwiązań:
1. za pomocą k monet ułożyć na wszystkie sposoby wszystkie kwoty do n - monetę m
trzeba wybrać jeśli z mniejszych wybranych nie da się złożyć m
2. wybrać na wszystkie sposoby k monet z przedziału [50 - n, 50] tak aby
używając potem mniejszych monet nie stracić możliwości ułożenia jakiejś sumy -
tracimy jeśli sumy nie da się ułożyć z wybranych monet i suma jest większa niż
50 + (50 - n) - wtedy z mniejsze monety już nie pomogą

Programiki oczywiście korzystały z podpowiedzi czyli szukały tylko rozwiązań
zgodnych z 1,3,...,47,49,50. Za pomocą tych programów szacowałem (uruchamiając
je z różnymi parametrami) ile co najmniej monet musi być wybranych spośród
pierwszych n oraz ostatnich n. Później wybrałem następujące wyniki:
1. musi być co najmniej 5 monet z przedziału 1..16
2. musi być co najmniej 9 monet z przedziału 18..50

Pozostały do zbadania następujące przypadki:
1) 5 z 1..16 (1 możliwość), 17, 10 z 18..50 (1284 możliwości)
2) 6 z 1..16 (71), 17, 9 z 18..50 (1)
3) 5 z 1..16 (1), 11 z 18..50 (51527)
4) 6 z 1..16 (71), 10 z 18..50 (1284)
5) 7 z 1..16 (410), 1 z 18..50 (1)
Razem 144456 możliwości - każdą trzeba sprawdzić biorąc odpowiedni zbiór monet i
patrząc czy da się ułożyć wszystkie sumy 1..100. Rozwiązanie było w przypadku 4.

Przy okazji poszukiwań dostałem zadziwiające wyniki:
6 monet z 1..20 oraz 7 monet z 30..50 można wybrać na 4 sposoby
7 z 1..20 oraz 8 z 30..50 na 274
8 z 1..20 oraz 9 z 30..50 na 2261
8 z 24..50 oraz 7 z 1..26 na 2
9 z 24..50 oraz 8 z 1..26 na 533
10 z 24..50 oraz 9 z 1..26 na 11539
Ciekawe? Zwłaszcza, że 50-30=20 i 50-24=26. Ale już chyba nie będę dociekał
dlaczego tak wyszło. To zadanie dla bardziej matematycznego umysłu bo ja to
jestem człowiek praktyczny (nie licząc rozwiązywania nikomu nie potrzebnych
łamigłówek :-).

> Liczby monet raczej nie da się zmniejszyć. Rozwiązanie jest identyczne z moim,
> co utwierdza mnie w przekonaniu, że jest tylko jedna możliwość. Jeszcze raz Ci
> gratuluję.

W końcowej fazie sprawdziłem tylko ok. 108 z 144 tysięcy możliwości aby znaleźć
rozwiązanie. Teraz sprawdziłem też pozostałe i faktycznie nie ma innego
rozwiązania z 16 monetami i też wydaje mi się, że z mniejszą liczbą nie wyjdzie.

pozdrawiam,
Tomek

[cardemon]

Doskonale! Też gratuluję Stomkowi odgadnięcia układu 16 monet, a Antypowi za
zamieszczenie tej łamigłówki.

pzdr. CdM

[kopperek]

I ja gratuluję.

kopperek

[Gość: ALP]

Ja rowniez przylaczam sie do gratulacji :)

[mesquaki]

Mądrzy ludzie z pomocą mądrych maszyn wynaleźli jeszcze 4 inne 16-monetowe
rozwiązania, ale to jest jedyne z przedziału 1-50.

podziwiam obecnych i pozdrawiam serdecznie
mes

[uller]

Ja też gratuluję.
W weekend nawet zarwałem całą noc aby rozwiązać to zadanie i nic. Uparłem się
że znajdę rozwiązanie bez komputera i się nie udało.
Jeszcze raz gratuluję i rozwiązania i zagadki.

Dzięki za uznanie

[stomek]

Czuję się zobowiązany podziękować za te wszystkie otrzymane od Was gratulacje (i
z góry dziękuję za te, które jeszcze otrzymam).

pozdrawiam,
Tomek