Задача
На всех клетках шахматной доски 8×8 расставлены натуральные числа. Разрешается выделить любой квадрат размером 3×3 или 4×4 и увеличить все числа в нём на 1. Мы хотим в результате нескольких таких операций добиться, чтобы числа во всех клетках делились на 10. Всегда ли это удастся сделать?
Решение
Будем записывать в таблицу только последние цифры (остатки от деления на 10). Заметим, что порядок проведения операций неважен, а важен только набор операций. Более того, так как десятикратное выполнение операции в одном квадрате ничего не меняет, операцию в каждом квадрате имеет смысл проводить не более 10 раз. Всего на доске (8 – 3 + 1)² = 36 квадратов 3×3 и 25 квадратов 4×4. Следовательно, из каждой таблицы может получиться не более чем 1025+36 = 1061 различных таблиц. Значит, таблицу из одних нулей можно получить не более чем из 1061 таблиц (если из таблицы A можно получить нулевую таблицу, то и из нулевой таблицы можно получить таблицу A), что меньше общего количества таблиц 1064.
Ответ
Не всегда.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь