Question

Крокодил Гена играет сам с собой в такую игру: у него есть мешок, в котором лежит 512 конфет. Он может или взять из мешка 300 конфет или положить в него 198 конфет. Других конфет, кроме как в мешке, у крокодила нет. Какое наибольшее количество конфет может оказаться вне мешка после того, как игра закончится? Комментарий. Если крокодил один раз возьмет 300 конфет и на этом игру закончит, то вне мешка будет 300 конфет.

Answer 1

Если посмотреть несколько первых шагов игры- на каждом шаге чаще всего можно сделать только один вариант действия: либо взять 300 конфет, либо вернуть 198.
Только на 5, 10 и 83 шагах игры доступны два варианта действия.Причём, на пятом шаге без разницы что выбирать- это повлияет только на распределение конфет на самом пятом шаге (на следующие шаги не влияет!).
На десятом шаге, при выборе первого варианта действия (взять 300 конфет) мы получаем максимальное число конфет у Гены за всю игру- 510 штук. Выбор второго варианта (вернуть 198 конфет) опять влияет только на результаты этого шага (вместо 510 получится 12).


Я продолжил эту последовательность в таблице в экселе (она приложена к решению), и получил, что на 84-ом шаге игра приходит к логическому концу- возвращается к состоянию первого шага- 212 в мешке и 300 у Гены.То есть, дальше игра идёт по кругу, с повтором значений, и продолжать нет смысла.
На 83-ем шаге, выбор второго варианта только сократит игру (она закончится уже на этом шаге, повторив исходное распределение конфет)
Ответ: наибольшее количество конфет вне мешка равно 510.

8d3ef2415ac9f87a0e1e8ec5b9bdcdf0.xls