задачка

[avva]

По внутренней рассылке прислали задачку. Очень может быть, что нетривиальную; решения я не знаю. Звучит красиво... думаю.

Пусть у нас есть какой-то набор достоинств монет, так, что любую сумму можно собрать из монет данного набора (количество индивидуальных монет каждого достоинства неограничено). Для любой суммы, чтобы собрать ее посредством данного набора, можно воспользоваться "жадным" алгоритмом: каждый раз брать наибольшую возможную монету, меньшую оставшейся суммы, вычитать ее, и продолжать так, пока ничего не останется.

Есть наборы, для которых "жадный" алгоритм всегда приведет к наименьшему возможному количеству монет (скажем, набор из 10, 5, 3 и 1 - такой). А есть наборы, для которых иногда можно воспользоваться меньшим количеством монет, чем дает "жадный" алгоритм (например, набор достоинств в 25, 20, 10, 5 и 1 такой: сумму в 40 денежных единиц можно в нем выразить двумя монетами по 20, а "жадный" алгоритм дает три монеты: 25, 10 и 5).

Вопрос: как для любого набора определить, к какой из этих двух групп он относится, т.е. всегда ли жадный алгоритм дает для него наименьшее количество монет?

P.S. Если вы просто знаете правильное решение (а не придумали его сами), не надо им делиться пока, хочу подумать сам.

Comments

[occuserpens.livejournal.com]

Сдается мне, что в общем виде, для любого набора монет, это очень "нечестная" задача, т.е. за ней стоит серьезный результат. Если не прав, смело бейте меня ногами.

[knop.livejournal.com]

Я не очень знаю, что такое "нечестная" задача.
Результат, который я в ней знаю - да, вполне приличный.
Но, между прочем, получен он был школьником 10-го класса

[relf.livejournal.com]

Так решена ли задача в полном объеме?
Девять лет назад ты говорил про какие-то частные решения...

[knop.livejournal.com]

да нет, вроде полностью все и тогда было...

[relf.livejournal.com]

Что же ты тогда подразумевал под "частичным ответом"?

Далее можно спросить, а сколько же величин достаточно проверять для общего случая при четырех монетах, пяти и т.д. Частичный ответ я знаю - когда-то очень активно занимался именно этой задачей. Так что предлагаю всем поразмышлять и сделать маленькое математическое открытие самостоятельно...

[knop.livejournal.com]

Я уж не помню, почему я тогда писал так. Чего ты от меня хочешь?..

По фактам.
Задача "Монетные системы" была предложена мной летом 1993 года на летней конференции Турнира Городов. Она есть в сборнике материалов той конференции, но, кажется, у этого сборника полная электронная версия утеряна (хотя, несомненно, была). Задача об определении критериев _удобности_ монетных систем (i.e. ровно то, о чем вы говорили тогда в ru.math и сейчас тут) была подзадачей 4.7. Честно говоря, когда я ее давал, я не рассчитывал получить от детей полное и исчерпывающее решение. Тем не менее, оно было получено: один из школьников (Олег Попов) сформулировал критерий и попробовал его нам аккуратно доказать. Аккуратно у него не получилось, но мы (Миша Вялый и я) по крайней мере поняли, как заделывать все шероховатости.

У меня есть оба теховских файла по этой задаче, которые я отправлял тогда публикаторам сборника - и условия, и решения. В принципе, я готов положить их в открытый доступ и сегодня вечером это точно сделаю.

Все.

[relf.livejournal.com]

Просто тогда в 1998 году из твоих слов у меня сложилось впечатление, что полное решение задачи неизвестно (хотя тут еще надо уточнять, что является решением). Получается, что я неправильно тебя понял. В любом случае спасибо за разъяснения.
А тех-файлы безусловно интересны, жду с нетерпением.

Дальнейшая история

[kohomologie.livejournal.com]

А потом Александр Кулаков и Михаил Вялый aka mnvyy сказали мне, чтобы я написал английскую статью про это решение, её куда-то посылали, но рецензия была такая: «Честно говоря, результат, полученный О. Поповым, меня не очень впечатлил. Может, переформулировать это в матроидном духе?» Так что у меня тоже есть TeX-файл, который я могу куда-нибудь выложить :). Если Вы свой выложили, дайте ссылку.

С тех пор я успел побывать будущим коммутативным алгебраистом, и мне показалось, что это скорее похоже не на матроиды, а на критерий Бухбергера того, что данное множество является базисом Грёбнера, но до содержательных утверждений я это не додумал.

Re: Дальнейшая история

[knop.livejournal.com]

Я тоже собирался (когда-то) вплотную обдумать, не является ли критерий Попова какой-то тривиальной переформулировкой чего-то алгебраического, но так и не собрался. А вот ребята англоязычники (см. ниже по ветке ссылочку на pdf-файл из citeseer'а) обдумали и опубликовали свой результат в статье. Ровно на год позже. По первому чтению - результаты эквивалентные. В детали я еще не вчитывался.

Кстати, покажите Мише эту дискуссию...

Re: Дальнейшая история

[kohomologie.livejournal.com]

Спасибо за ссылку ниже! pdf c citeseer'а прочитал, критерий, насколько помню, именно тот, но представления его как частного случая чего-то общеалгебраического в статье не обнаружил.

Ссылку Мих. Ник. я послал сразу же.

Re: Дальнейшая история

[knop.livejournal.com]

Критерий в самом деле тот же. Автор критерия - больше компьютер сайентист, чем математик, поэтому ждать от него какой-то алгебры не приходится.
Я потом нашел на citeseer еще одну (более позднюю) статью, в которой тоже нет серьезной математики, но по крайней мере там внятно изложен список имеющихся результатов, а также интересных (и нерешенных) задач. У статьи очень смешной заголовок - типа "Все, что на самом деле нужно стране - это монета достоинством 18 центов".
http://citeseer.ist.psu.edu/shallit02what.html