Олимпиадная задача по теории алгоритмов: Винни-Пух, Кролик и Пятачок с орехами
Задача
На столе стоят три пустых банки из-под меда. Винни-Пух, Кролик и Пятачок по очереди кладут по одному ореху в одну из банок. Их порядковые номера до начала игры определяются жребием. При этом Винни может добавлять орех только в первую или вторую банку, Кролик – только во вторую или третью, а Пятачок – в первую или третью. Тот, после чьего хода в какой-нибудь банке оказалось ровно 1999 орехов, проигрывает. Докажите, что Винни-Пух и Пятачок могут, договорившись, играть так, чтобы Кролик проиграл.
Решение
Пусть Винни и Пятачок вначале кладут свои орехи во вторую и третью банки, не смотря на ходы Кролика, до тех пор, пока в одной из банок не станет 1998 орехов. После этого тот, кто должен класть орехи в эту банку (пусть, например, это Винни) начинает класть их вI. При этом он уже положил воIIбанку не менее 999 орехов, значит, вIIIорехов тоже не менее 999 (туда их клал Пятачок). После этого Пятачок продолжает класть вIIIбанку орехи, пока там не станет 1998 – это произойдет не более, чем через 500 ходов, так как вIIIбанку также приходится класть орехи Кролику, чтобы не проиграть. После этого Пятачок также может класть орехи вIбанку, так как там не более 500 орехов, положенных Винни, а Кролик вынужден будет положить орех воIIилиIII, где их уже по 1998.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь