Олимпиада имени Леонарда Эйлера 2017-2018 учебный год, II тур регионального этапа
Комментарий/решение:
Комментарии от администратора Комментарии от администратора №1. Решение. Оценка. Заметим, что если в строчке закрашено 9 клеток, то можно перекрасить четыре из них так, чтобы никакие две закрашенные клетки не были соседними: достаточно перенумеровать закрашенные клетки слева направо и перекрасить клетки с чётными номерами. Если сделать такие перекрашивания со всеми чётными строками, то перекрасится 48 клеток и не будет закрашенных квадратов 2×2, поскольку не будет двух соседних закрашенных клеток в одной чётной строке.
Пример. Закрасим расположенные вдоль главной диагонали непересекающиеся квадраты: первый со стороной 9 и два со стороной 8 --- и клетки, расположенные по незакрашенной главной диагонали квадрата 16×16, содержащего квадраты 8×8. Тогда на доске можно будет выделить 48 не пересекающихся квадратов 2×2, все клетки которых закрашены. Поэтому в этом примере надо перекрасить не менее 48 клеток.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.