2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Через тернии к шахматной раскраске - II
Сообщение30.08.2019, 07:56 
Аватара пользователя
Пока добрался до $6$-ти.

 
 
 
 Re: Через тернии к шахматной раскраске - II
Сообщение30.08.2019, 21:57 
Аватара пользователя
За $6$ тоже получилось:$$3UL\rightarrow3DR\rightarrow1UL\rightarrow1DR\rightarrow2DL\rightarrow2DR$$Цифра для каждого шага обозначает размер квадрата, а буквы - какой угол квадрата $4\times4$ включается в перекраску

 
 
 
 Re: Через тернии к шахматной раскраске - II
Сообщение30.08.2019, 22:38 
waxtep
Получилась доска, лежащая "на боку". 8-)
Принято, что левая нижняя клетка $a1$ — черная.

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

-- 30.08.2019, 23:49 --

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

 
 
 
 Re: Через тернии к шахматной раскраске - II
Сообщение01.09.2019, 10:00 
Аватара пользователя
А за 5 (или менее) никак?

 
 
 
 Re: Через тернии к шахматной раскраске - II
Сообщение01.09.2019, 10:56 
Аватара пользователя
Меньше 5 нельзя.
Назовем стеной сторону, разделяющую две клетки разных цветов.
Рассмотрим стены между клетками на границе доски.
В исходной конфигурации 2 таких стены, в конечной - все 12.
Каждый квадрат создает максимум две стены на границе.
Значит, нужно минимум 5 квадратов.

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

 
 
 
 Re: Через тернии к шахматной раскраске - II
Сообщение02.09.2019, 16:22 
Аватара пользователя
Xaositect
Большое спасибо!

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group