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

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

Условие

На столе в ряд лежат 20 плюшек с сахаром и 20 с корицей в произвольном порядке. Малыш и Карлсон берут их по очереди, начинает Малыш. За ход можно взять одну плюшку с любого края. Малыш хочет, чтобы ему в итоге досталось по десять плюшек каждого вида, а Карлсон пытается ему помешать. При любом ли начальном расположении плюшек Малыш может достичь своей цели, как бы ни действовал Карлсон?


Решение

  Пронумеруем плюшки в ряду числами от 1 до 40. Заметим, что у Малыша всегда есть возможность взять плюшку с номером любой чётности, а после каждого его хода Карлсон вынужден брать плюшку с номером другой чётности.
  Пусть среди плюшек с нечётными номерами не меньше десяти с сахаром (если с корицей, то рассуждения аналогичны). Тогда Малыш начинает с того, что берёт плюшки с нечётными номерами и после каждого хода Карлсона вычисляет такую величину: количество полученных плюшек с сахаром + количество оставшихся на столе плюшек с сахаром с чётными номерами. В начальный момент эта величина не больше 10, а если Малыш будет брать плюшки только с нечётными номерами, то в конце она будет не меньше 10. При этом после каждой пары ходов Малыша и Карлсона эта величина изменяется не более чем на 1. Следовательно, в какой-то момент (возможно, начальный) она будет равна 10. После этого Малыш может брать только плюшки с чётными номерами и в итоге получит ровно 10 плюшек с сахаром, а значит, и 10 плюшек с корицей, что и требуется.


Ответ

При любом.

Замечания

  1. Верно более общее утверждение: если в ряд лежит чётное число плюшек, и из них на нечётных местах ровно L с сахаром, а на чётных – ровно R с сахаром, то для всякого k между (нестрого) числами R и L Малыш может действовать так, чтобы взять ровно k плюшек с сахаром.
  Для решения исходной задачи достаточно доказать это утверждение, ибо в нашем случае  R+L=20  и одно из чисел не меньше 10, а другое не больше 10.
  Индукция по количеству плюшек. Если их две, утверждение очевидно.
  Шаг индукции. Покрасим плюшки в шахматном порядке так, чтобы нечётные стали белыми. Если  k=L,  то Малышу достаточно каждым ходом есть белую плюшку, если  k=R  – чёрную. Если же k заключено строго между L и R, то Малыш может сделать первый ход произвольно, а далее добиться своего по предположению индукции. В самом деле, не умаляя общности,  L<k<R,  тогда белых плюшек с сахаром останется либо L, либо  L – 1 , чёрных – либо R, либо  R – 1,  а Малышу далее надо взять либо k, либо  k – 1  плюшку с сахаром, причём  L1<L.

2. 12 баллов.

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

олимпиада
Название Турнир городов
год/номер
Номер 43
Дата 2021/22
вариант
Вариант осенний тур, сложный вариант, 8-9 класс
задача
Номер 7
олимпиада
Название Турнир городов
год/номер
Номер 43
Дата 2021/22
вариант
Вариант осенний тур, сложный вариант, 10-11 класс
задача
Номер 6

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

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