* Монетният двор на Англия
Публикувано на 31 декември 2008 в раздел Математика.
В монетният двор на Англия решили, че наличните разновидности златни монети не са оптимални. Хората най-често пазарували дребни неща за суми от 1 до 20 лири. В моментното състояние (златни монети от 1, 2, 5 и 10 лири) за плащане от 18 лири е нужно да дадат една монета от 10, една от пет, една от 2 и една от 1 лира, т.е. общо 4 монети! Джобовете на хората често се късали и за това е било нужно спешно решение.
Кралят на Англия дал задачата на виден математик (в случая това сте вие). Намерете минималният брой различни стойности на монети, такъв, че всяка една сума от 1 до 20 лири да може да се заплати с максимум две монети, без да има нужда от връщане на ресто. Напишете като коментар различните видове монети.
Ще трябват доста монети.
Значи първо нека видим проблемните числа при съществуващите монети 1,2,5 и 10
8 - 5 и 2 и 1.
9 - 5 и два пъти по две в най-лекия случай
13 - 10 и 2 и 1
14 - 10 и два пъти по две в най-лекия случай
16 - 10 и 5 и 1 в най-лекия случай
17,18 и 19 и те.
Така предлагам да се запази сегашната система с 1,2,5 и 10 но да се добави 3.
За да се оправи проблема с 8. 5 и 3 прави 8.
3 решава и проблема с 13 (10 и 3 прави 13)
Остава девет, нека се добави и монета от 4.
Значи 4 решава проблема с 9 (5 и 4). Както и с 14 (10 и 4).
Но може числото да е и 7 (7 и 2 прави 9) два пъти по 7 прави 14.
Останаха като проблемни 16,17,18 и 19.
Добавя се цяло 16, а с 1 2 и 3 в добавка прави горните числа.
Тоест трябват ни 3, 4 или 7 и 16 плюс съществуващите вече 1,2,5 и 10.
10 и 10.
Тоест казваш, че трябва да има само една монета със стойност 10? Не изпълнява условието, защото не можеш да платиш следните суми:
1, 2, 3, ..., 9, 11, 12, ..., 18 и 19 :)
Може би не си разбрал условието.
Малко трябва да поопростиш нещата, сега малко се обърках с логическите ти "и" и "или".
Минималният брой различни монети е 7, съответно от по 1, 2, 3, 7, 8, 9, 10 лири. Тогава сумите се образуват така:
4 лири =2+2 =1+3
5 лири =2+3
6 = 3+3
11= 10+1
12= 10+2
13= 10+3
14= 7+7
15= 7+8
16= 8+8 =7+9
17= 7+10 =8+9
18= 9+9 =10+8
19= 10+9.
Обаче това едва ли е решило въпроса с късането на джобовете :)
ако се запазят досега съществуващите 1,2,5 и 10 и добавим 8 и 9 се получава:
1-ОК; 2-ОК; 3=1+2; 4=2+2; 5-ОК; 6=5+1; 7=5+2; 8-ОК; 9-ОК; 10-ОК; 11=10+1; 12=10+2; 13=8+5; 14=9+5; 15=10+5; 16=8+8; 17=9+8; 18=10+8; 19=10+9; 20=10+10, т.е. общият брой на монетите става 6.
sdiankov - Браво! Верният отговор наистина е 6 монети и ти откри една от възможните комбинации!
За останалите разяснявам как би трябвало да се достигне до решението. Първо ще кажа, че от математическа гледна точка не би било добре да използваме съществуващите монети, тъй като те правят повторения:
2 = 2
2 = 1+1
10 = 10
10 = 5+5
Тъй като търсим минимум, то определено би трябвало да се стремим да избегнем повторенията.
Затова в моето решение ще започна "от нулата". Първата сума, която трябва да покрия е 1. Друга монета освен стойност 1 не може да я покрие. Затова първата избрана монета ще е задължително 1. Тя покрива следните суми:
1 = 1
2 = 1+1
но виждаме, че не може да покрие сумата 3. Затова слагаме монета с номинална стойност 3:
1 = 1
2 = 1+1
3 = 3
4 = 3+1
Виждаме, че 1,3 не покрива сума 5. Слагаме монета с номинал 5:
1 = 1
2 = 1+1
...
5 = 5
6 = 5+1 или 3+3
Виждаме, че 1,3,5 не покрива сума 7. Слагаме монета 7:
1 = 1
...
6 = 5+1
7 = 7
8 = 7+1 или 8+3
Монетите 1,3,5,7 за съжаление не успяха да покрият сума 9. Ще се наложи да я сложим. Тук дори няма да изброявам възможностите, защото е ясно, че максималната сума, която се покрива от тези монети е 18 = 9+9, т.е. те отново не са достатъчни. Слагам монета 10 и всичко е готово:
1,3,5,7,9,10 покриват всички възможности. Ако искате - проверете.
Истината е, че един математик ще се опита яростно да реши задачата с 5 монети, защото:
1 монета прави 2 комбинации
2 монети правят 4 комбинации
3 монети правят 9 комбинации
4 монети правят 18 комбинации
=> добавяйки пета монета би трябвало да имаме предостатъчно комбинации. За съжаление по метода на покриване на най-малката сума (който демонстрирах) се оказва недостатъчно...
не се задълбавах чак толкова, но първото, което ми хрумна бяха: 1,2,3,4,5 и 10.... та това ми се струва много по-опростен вариант.. :)
martin: С тези монети не можеш да направиш суми 16, 17, 18 и 19
За да се спази условието всички тези суми да могат да се платят с не повече от две монети минималният брой различни стойности на монети е 7, а именно 1, 2, 3, 4, 5, 11 и 17