Через тернии к шахматной раскраске - II

[Ktina]

В квадрате $4\times 4$ клетки левой половины покрашены в чёрный цвет, а остальные – в белый.
За одну операцию разрешается перекрасить в противоположный цвет все клетки внутри любого квадрата $n\times n,\; 1\leqslant n\leqslant 4$.
За какое наименьшее число операций из первоначальной раскраски можно получить шахматную?

[Утундрий]

Пока добрался до $6$-ти.

[waxtep]

За $6$ тоже получилось:

$$3UL\rightarrow3DR\rightarrow1UL\rightarrow1DR\rightarrow2DL\rightarrow2DR$$

Цифра для каждого шага обозначает размер квадрата, а буквы - какой угол квадрата $4\times4$ включается в перекраску

[Booker48]

waxtep
Получилась доска, лежащая "на боку".
Принято, что левая нижняя клетка $a1$ — черная.

[waxtep]

Booker48, тут же вообще страшное дело: $75\%$ поля украдено до нас!
Можно еще таким забавным способом за шесть ходов: $22_2,12_2,21,24,41,44$; теперь, две цифры - координаты верхнего левого угла квадрата (нумерация с единицы сверху вниз и слева направо), а нижний индекс - размер квадрата; если индекса нет, то он единичка

-- 30.08.2019, 23:49 --

И совсем маниакальный способ (всюду размер квадрата - $2\times2$): $12,32,21,23,31,33$

[Ktina]

А за 5 (или менее) никак?

[Xaositect]

Меньше 5 нельзя.
Назовем стеной сторону, разделяющую две клетки разных цветов.
Рассмотрим стены между клетками на границе доски.
В исходной конфигурации 2 таких стены, в конечной - все 12.
Каждый квадрат создает максимум две стены на границе.
Значит, нужно минимум 5 квадратов.

Перебрав все варианты построения стен, можно доказать, что и за 5 нельзя, но красивого доказательства не придумалось.

[Ktina]

Xaositect
Большое спасибо!