Выбрана 1 задача 
Убрать все задачи
В белой таблице 2016×2016 некоторые клетки окрасили чёрным. Назовём натуральное число k удачным, если k ≤ 2016, и в каждом из клетчатых квадратов со стороной k, расположенных в таблице, окрашено ровно k клеток. (Например, если все клетки чёрные, то удачным является только число 1.) Какое наибольшее количество чисел могут быть удачными?
Решение
|
|
 |
Условие
На столе в ряд лежат 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 плюшку с сахаром, причём $L -1 < L \leqslant k - 1 < k \leqslant R - 1 < R$.
2. 12 баллов.
