Можно ли раскрасить доску 8×8 по условиям задачи Пушкаря — олимпиадная задача по комбинаторной геометрии

Ответ: нельзя.Решение. Предположим, что такая раскраска возможна. На всех рисунках не заштрихованы клетки, про которые выяснено, что они не закрашены; штриховкой обозначены клетки, про которые ещё не известно, закрашены они или нет; двойной штриховкой - заведомо закрашенные. Рис. 11 Доску 8*8 можно разрезать на восемь прямоугольников 4×2, поэтому на ней ровно 8×4=32 закрашенные клетки. Также её можно разрезать на четыре квадрата 3×3, три прямоугольника 4×2 и угловой квадратик 2×2 (рис. 11). В четырёх квадратах 3×3 и трёх прямоугольниках 4×2 уже 4×5+3×4=32 клетки, поэтому в угловом квадратике 2×2 не должно быть ни одной закрашенной клетки. Аналогично можно доказать, что и в остальных угловых квадратиках 2×2 нет закрашенных клеток. Рис. 12 Доску без угловых квадратиков 2×2 можно разрезать на шесть прямоугольников 4×2 (рис. 12). Получаем, что всего на доске 6×4=24 закрашенные клетки. Противоречие. Примечание. Доказав, что угловые квадратики 2×2 не закрашены, можно действовать и по-другому, например, так. Разместим на доске четыре квадрата 3×3 и два прямоугольника 4×2 как показано на рис. 13. На оставшееся место приходится 32-(4×5+2×4)=4 закрашенные клетки, и туда можно поместить два прямоугольника 4×2, перекрывающиеся по квадратику 2×2. В каждом из них четыре закрашенные клетки, и вместе у них четыре закрашенных клетки - значит, закрашено их пересечение, и угловой квадратик 2×2 должен быть полностью закрашен. Противоречие. Приведём ещё одно решение. Покажем, что даже доску 6×6 нельзя раскрасить указанным в задаче образом. Так как её можно разрезать на четыре квадрата 3×3, в ней должно быть ровно 4×5=20 закрашенных клеток. Разрежем её на четыре прямоугольника 4×2 и квадратик 2×2 (рис. 14). В этих прямоугольниках 4×4=16 клеток, значит в 2×2 сосредоточены остальные 20-16=4 клетки, т. е. все клетки в нём закрашены. Рис. 13 Переложив четыре прямоугольника другим образом, можно то же самое доказать про квадратики 2×2 в других углах, а также про квадратик в центре (рис. 15). Остальные клетки должны быть незакрашенными, так как в каждом прямоугольнике 4×2 уже есть по четыре закрашенные клетки. Теперь легко указать квадрат 3×3, в котором всего четыре закрашенные клетки (рис. 16).

Рис 14.	Рис 15.	Рис 16.

Ответ задачи отсутствует