Задача 4.
В центральной клетке доски 21 × 21 находится фишка. За один ход можно передвинуть фишку в соседнюю по стороне клетку. Алина сделала 10 ходов. Сколько существует клеток, где может оказаться фишка?
Ответ на Задачу 4.
Ответ: 121.
Решение:
Покрасим всю доску в шахматную раскраску так, чтобы центральная клетка доски была чёрной. При передвижении фишки в соседнюю по стороне клетку каждый раз будет меняться цвет клетки, на которой стоит фишка. Спустя нечётное число ходов фишка всегда оказывается на белой клетке, а спустя чётное число ходов — на чёрной. Следовательно, после 10 ходов фишка точно окажется на чёрной клетке.
Покажем, что во все чёрные клетки, в которые возможно попасть не более, чем за 10 ходов, можно попасть и ровно за 10 ходов. Рассмотрим произвольную чёрную клетку 𝐴, в которую можно попасть менее чем за 10 ходов из центральной. Поскольку к моменту попадания в клетку 𝐴 было сделано чётное количество ходов, меньшее 10, то дальше можно просто передвигать фишку в соседнюю клетку и обратно, пока не будет сделано ровно 10 ходов. Значит, нам надо посчитать количество чёрных клеток, в которые можно попасть не более чем за 10 ходов.
За 0 ходов можно попасть только в начальную клетку, за 2 хода можно попасть в начальную клетку и в 4 ⋅ 2 = 8 новых клеток, за 4 хода можно попасть в те клетки, в которые уже попадали, и в 4 ⋅ 4 = 16 новых клеток и так далее. Получаем, что количество клеток, в которые можно попасть не более чем за 10 шагов, равно 1 + 8 + 16 + 24 + … + 40 = 1 + 8(1 + 2 + 3 + 4 + 5) = 121.
Замечание: Центры клеток, в которые можно попасть за 𝑘 ≤ 10 шагов, образуют вершины квадратной решетки, повёрнутой на 45° (см. рисунок). Отсюда ясно, что всего таких клеток 112.
