Метод математической индукции один из мощнейших методов доказательств в математике. И вот еще одна задача на этот прекрасный метод. Предыдущие задачи по теме: Задача 28, Задача 24.
Условие:
Какое наибольшее число клеток клетчатого квадрата (2n-1)*(2n-1) можно закрасить так, чтобы никакие три закрашенные клетки не образовывали уголок из трех клеток?
Решение:
В случае раскраски приведенной ниже, будет покрашено n(2n-1) клеток.
Докажем индукцией по n, что не удастся покрасить большее число клеток. База индукции. Для n=1 - очевидно.
Предположение индукции. Пусть верно для n=k.
Шаг индукции. Докажем для n=k+1. Квадрат (2(k+1)-1)*(2(k+1)-1) разбивается на квадрат (2k+1)*(2k+1), и угол толщиной в две клетки. Угол разобьем на 2k-1 квадратиков 2*2, один уголок из трех клеток и одну клетку.
В квадратике 2*2 должно быть не более двух закрашенных клеток. Итого в угле не более чем 2(2k-1)+2+1=4k+1 закрашенных клеток. В квадрате (2k+1)*(2k+1) не более k(2k-1) закрашенных клеток по предположению индукции. Поэтому в квадрате (2(k+1)-1)*(2(k+1)-1) не более k(2k-1)+4k+1=(k+1)(2(k+1)-1) закрашенных клеток. Утверждение доказано.
Всем кто дочитал, спасибо за внимание! Удачных вам вычислений!
