Не могу не поздравить всю математическую общественность с 300-летием со дня рождения выдающегося российского математика Леонарда Эйлера. Выпьем, товарищи!

Недавно ехал в Москву, и по вагонам пошли контроллёры, коротые честно проверяли все магнитные карты на действительность. Бегать из вагона в вагон я не привык, поэтому спокойно дождался того момента, как мне предложили заплатить за проезд на участке Крюково — П.-Разумовское. Деваться некуда — достал 100 рублей, отдал. Сдачи получил не больше не меньше, а ровно 51 рубль. Но вместо обычной красной квитанции (на заднем плане) я получил солидную ленту билетов достоинством в 0.5, 1, 3 и 10 рублей.

В голове математика сразу же родилась следующая задача, правда я ещё не интересовался, не приходила ли она кому-то в голову до меня и тогда не решена ли она уже.

Есть k типов билетов, которыми надо выдать любую сумму от 0 до M рублей с шагом d. Каковы должны быть номиналы билетов, чтобы максимальное число выданных билетов было минимальным? Чтобы среднее число выдаваемых билетов было минимальным?

Куплю в скором времени:

 Почему-то о многом хочется высказаться, но оставлю пока в себе.