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

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

Условие

Победив Кащея, потребовал Иван золота, чтобы выкупить Василису у разбойников. Привёл его Кащей в пещеру и сказал: "В сундуке лежат золотые слитки. Но просто так их унести нельзя: они заколдованы. Переложи себе в суму один или несколько. Потом я переложу из сумы в сундук один или несколько, но обязательно другое число. Так мы будем по очереди перекладывать их: ты в суму, я в сундук, каждый раз новое число. Когда новое перекладывание станет невозможным, сможешь унести свою суму со слитками". Какое наибольшее число слитков может унести Иван, как бы ни действовал Кащей, если в сундуке исходно лежит  а) 13;  б) 14 золотых слитков? Как ему это сделать?


Решение

  Иван будет действовать так, что каждый раз ход Кащея будет единственным: все остальные числа либо встречались на предыдущих ходах, либо слишком велики – у Ивана в этот момент нет такого количества слитков. Будем записывать ходы игры следующим образом:
     количество переложенных слитков (число слитков у Ивана после хода).

  а)  2 (2), 1 (1), 3 (4), 4 (0), 6 (6), 5 (1), 7 (8), 8 (0), 10 (10), 9 (1), 11 (12), 12 (0), 13 (13).
  Все возможные ходы сделаны, у Ивана все 13 слитков, значит, их он может забрать.

  б) Будем действовать так же, как в предыдущем пункте. После хода "13 (13)" не сделан только ход 14, но он невозможен, поэтому Иван может унести 13 слитков.
  Докажем, что 14 слитков Иван унести не может. Допустим, в какой-то момент в сумке оказалось 14 слитков. Значит, в сундуке слитков нет, то есть последним ходил Иван. Но тогда всего сделано нечётное число ходов, и поэтому какое-то из чисел от 1 до 14 не встретилось. Кащей может сделать ход с этим числом, значит, уносить слитки пока нельзя.


Ответ

а) 13;   б) 13 слитков.

Замечания

1. 8 баллов за оба пункта, 5 баллов за один.

2. Для  4k + 1  слитка задача решается аналогично пункту а), а для  4k + 2  слитков – аналогично пункту б).

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

олимпиада
Название Математический праздник
год
Год 2012
Класс
Класс 7
задача
Номер 6

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

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