Комбинаторика, задача на раскраски

[prrrr]

Здравствуйте!
Задача такая:

Муха-Цокотуха купила на базаре шахматную доску размером 8×8. К Мухе пришли в гости тараканы и букашки. Тараканы выпилили из доски 8 квадратных кусков размером 2×2. Докажите, что букашки тоже смогут выпилить кусок размером 2×2 из оставшихся фрагментов доски.

Решение получилось такое:
Попробуем найти минимально возможное количество квадратов 2х2, которые тараканы могут вырезать из заданной доски 8х8.
Чтобы количество вырезанных квадратов 2х2 было минимально, нужно чтобы из оставшихся после вырезания квадрата 2х2 обрезков доски невозможно было вырезать квадрат 2х2. Это значит, что тараканы должны вырезать квадраты таким образом, чтобы между вырезанными квадратами и/или краем доски было поле шириной не более чем 1 клетка. Квадрат 2х2 плюс поле шириной 1 клетка рядом, в сумме дают 3х3 клетки. Получается, что квадраты, вырезанные тараканами, должны располагаться на полях размером 3х3.

Полностью таких полей по каждой стороне помещается по 2 и в этом случае по ширине и высоте всего помещается 4 вырезанных квадрата (общая ширина/высота 8 клеток, тогда по ширине и высоте: 3+3+2 клетки). Значит после вырезания 4х квадратов остается обрезок доски общей длиной 14 клеток и шириной 2 клетки. Из этого куска можно вырезать не менее 5 квадратов 2х2 (5 при условии, что квадраты вырезаны таким образом, что рядом с вырезанным квадратом остается поле шириной не более 1 клетки).

Таким образом, получается, что минимальное количество квадратов, которое можно вырезать, согласно заданным условиям – 9, тараканы вырезали 8 квадратов, значит букашки всегда смогут вырезать хотя бы 1 квадрат 2х2.


На это решение получил замечание:
"Это значит, что тараканы должны вырезать квадраты таким образом, чтобы между вырезанными квадратами и/или краем доски было поле шириной не более чем 1 клетка."
Не доказано, что они должны вырезать именно так и других вариантов нет.

Подскажите пожалуйста, как это можно доказать? Очевидно же, что рядом с квадратом должны оставаться куски шириной не более 1 клетки.. Понимаю, что один из вариантов наверное перебором всех вариантов размещения квадратов 2x2 на доске, но это точно не лучший вариант.
Заранее огромное спасибо!)

[TOTAL]

Восемь прямоуголников $1\times2$ без примыкания друг к другу расположите на расстоянии одной клетки от границы квадрата до широкой стороны.

[prrrr]

TOTAL в сообщении #1548828 писал(а):

Восемь прямоуголников $1\times2$ без примыкания друг к другу расположите на расстоянии одной клетки от границы квадрата до широкой стороны.

А почему $1\times2$? Ведь вырезают только $2\times2$? Так у меня получается в центре квадрат $4\times4$..

[TOTAL]

prrrr в сообщении #1548831 писал(а):

TOTAL в сообщении #1548828 писал(а):

Восемь прямоуголников $1\times2$ без примыкания друг к другу расположите на расстоянии одной клетки от границы квадрата до широкой стороны.

А почему $1\times2$? Ведь вырезают только $2\times2$? Так у меня получается в центре квадрат $4\times4$..

Каждый из $1\times2$ должен быть "покусан" вырезаемым квадратом (иначе он и граничные квадраты дадут $2\times2$)

-- Вт фев 15, 2022 09:48:54 --

Или так. Раскрасим девять квадратов $2\times 2$ так, чтобы они не касались друг друга. Каждый вырезаемый квадрат может повредить только один раскрашенный. Так что останется неповрежденный раскрашенный квадрат.

[prrrr]

TOTAL в сообщении #1548833 писал(а):

Каждый из $1\times2$ должен быть "покусан" вырезаемым квадратом (иначе он и граничные квадраты дадут $2\times2$)

-- Вт фев 15, 2022 09:48:54 --

Или так. Раскрасим девять квадратов $2\times 2$ так, чтобы они не касались друг друга. Каждый вырезаемый квадрат может повредить только один раскрашенный. Так что останется неповрежденный раскрашенный квадрат.

Теперь понял) Спасибо огромное!!