* Монетният двор на Англия

Публикувано на 31 декември 2008 от Филип Петров. Записано в Math.


В монетният двор на Англия решили, че наличните разновидности златни монети не са оптимални. Хората най-често пазарували дребни неща за суми от 1 до 20 лири. В моментното състояние (златни монети от 1, 2, 5 и 10 лири) за плащане от 18 лири е нужно да дадат една монета от 10, една от пет, една от 2 и една от 1 лира, т.е. общо 4 монети! Джобовете на хората често се късали и за това е било нужно спешно решение.

Кралят на Англия дал задачата на виден математик (в случая това сте вие). Намерете минималният брой различни стойности на монети, такъв, че всяка една сума от 1 до 20 лири да може да се заплати с максимум две монети, без да има нужда от връщане на ресто. Напишете като коментар различните видове монети.



10 коментара за “Монетният двор на Англия”

 
  1. Петър Дяков написа:
    31 декември 2008 на 19:11

    10 и 10.

     
  2. Филип Петров написа:
    31 декември 2008 на 19:12

    Тоест казваш, че трябва да има само една монета със стойност 10? Не изпълнява условието, защото не можеш да платиш следните суми:
    1, 2, 3, …, 9, 11, 12, …, 18 и 19 :)

    Може би не си разбрал условието.

     
  3. Мартин написа:
    31 декември 2008 на 19:56

    Ще трябват доста монети.

    Значи първо нека видим проблемните числа при съществуващите монети 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.

     
  4. Филип Петров написа:
    31 декември 2008 на 20:04

    Малко трябва да поопростиш нещата, сега малко се обърках с логическите ти „и“ и „или“.

     
  5. Малина написа:
    01 януари 2009 на 23:39

    Минималният брой различни монети е 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.
    Обаче това едва ли е решило въпроса с късането на джобовете :)

     
  6. sdiankov написа:
    02 януари 2009 на 9:55

    ако се запазят досега съществуващите 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.

     
  7. Филип Петров написа:
    02 януари 2009 на 10:45

    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 комбинации
    => добавяйки пета монета би трябвало да имаме предостатъчно комбинации. За съжаление по метода на покриване на най-малката сума (който демонстрирах) се оказва недостатъчно…

     
  8. martin написа:
    02 януари 2009 на 23:25

    не се задълбавах чак толкова, но първото, което ми хрумна бяха: 1,2,3,4,5 и 10…. та това ми се струва много по-опростен вариант.. :)

     
  9. Филип Петров написа:
    03 януари 2009 на 10:22

    martin: С тези монети не можеш да направиш суми 16, 17, 18 и 19

     
  10. Николай написа:
    16 януари 2009 на 14:42

    За да се спази условието всички тези суми да могат да се платят с не повече от две монети минималният брой различни стойности на монети е 7, а именно 1, 2, 3, 4, 5, 11 и 17

     

Trackback URI | RSS за коментарите

Пусни коментар


Страници

Категории

Нови

Връзки