Олимпиадная задача про делёж монет героями Хапоком и Глазком (8–9 класс, теория алгоритмов)
Задача
Разбойники Хапок и Глазок делят кучу из 100 монет. Хапок захватывает из кучи пригоршню монет, а Глазок, глядя на пригоршню, решает, кому из двоих она достается. Так продолжается, пока кто-то из них не получит девять пригоршней, после чего другой забирает все оставшиеся монеты (дележ может закончиться и тем, что монеты будут разделены прежде, чем кто-то получит девять пригоршней). Хапок может захватить в пригоршню сколько угодно монет. Какое наибольшее число монет он может гарантировать себе независимо от действий Глазка?
Решение
Вот стратегия Хапка, которая обеспечит ему не меньше 46 монет: брать каждый раз (пока это возможно) по шесть монет. В куче содержится 16 таких полных пригоршней и еще четыре монеты. При такой стратегии Хапка (как бы ни действовал Глазок) имеются только две возможности:
а) в какой-то момент у Глазка окажется девять полных пригоршней, делёж на этом закончится, и оставшиеся 46 монет окажутся у Хапка;
б) Глазок забирает себе не больше восьми полных пригоршней, значит, в какой-то момент Хапок получит восемь таких пригоршней; уже в этот момент у него будет не меньше 48 монет.
Стратегия Глазка, которая обеспечит ему не менее 54 монет (это означает, что Хапок не может гарантировать себе более 46 монет): те пригоршни, в которых меньше шести монет (маленькие), отдавать Хапку, а остальные (большие) брать себе. При такой стратегии Глазка (как бы ни действовал Хапок) также есть две возможности:
а) Глазок заберёт себе девять больших пригоршней, то есть у него будет не менее 54 монет;
б) Хапок получит девять или менее (если делёж закончился “досрочно”) маленьких пригоршней, то есть не более 45 монет.
Ответ
46 монет.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь