ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 98478
Тема:    [ Теория игр (прочее) ]
Сложность: 4
Классы: 8,9
В корзину
Прислать комментарий

Условие

Разбойники Хапок и Глазок делят кучу из 100 монет. Хапок захватывает из кучи пригоршню монет, а Глазок, глядя на пригоршню, решает, кому из двоих она достается. Так продолжается, пока кто-то из них не получит девять пригоршней, после чего другой забирает все оставшиеся монеты (дележ может закончиться и тем, что монеты будут разделены прежде, чем кто-то получит девять пригоршней). Хапок может захватить в пригоршню сколько угодно монет. Какое наибольшее число монет он может гарантировать себе независимо от действий Глазка?


Решение

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


Ответ

46 монет.

Замечания

1. Приведённая стратегия Хапка не единственна. Например, годится и такая: восемь раз взять по 5 монет, а затем брать по 6.

2. 7 баллов.

Источники и прецеденты использования

олимпиада
Название Турнир городов
Турнир
Дата 1999/2000
Номер 21
вариант
Вариант весенний тур, основной вариант, 8-9 класс
Задача
Номер 4

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .