2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Через тернии к шахматной раскраске - II
Сообщение30.08.2019, 01:31 
Аватара пользователя


01/12/11

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

 Профиль  
                  
 
 Re: Через тернии к шахматной раскраске - II
Сообщение30.08.2019, 07:56 
Заслуженный участник
Аватара пользователя


15/10/08
8426
Пока добрался до $6$-ти.

 Профиль  
                  
 
 Re: Через тернии к шахматной раскраске - II
Сообщение30.08.2019, 21:57 
Аватара пользователя


07/01/16
881
Аязьма
За $6$ тоже получилось:$$3UL\rightarrow3DR\rightarrow1UL\rightarrow1DR\rightarrow2DL\rightarrow2DR$$Цифра для каждого шага обозначает размер квадрата, а буквы - какой угол квадрата $4\times4$ включается в перекраску

 Профиль  
                  
 
 Re: Через тернии к шахматной раскраске - II
Сообщение30.08.2019, 22:38 


07/06/17
639
waxtep
Получилась доска, лежащая "на боку". 8-)
Принято, что левая нижняя клетка $a1$ — черная.

 Профиль  
                  
 
 Re: Через тернии к шахматной раскраске - II
Сообщение30.08.2019, 23:34 
Аватара пользователя


07/01/16
881
Аязьма
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 
Аватара пользователя


01/12/11

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

 Профиль  
                  
 
 Re: Через тернии к шахматной раскраске - II
Сообщение01.09.2019, 10:56 
Заслуженный участник
Аватара пользователя


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

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

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


01/12/11

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модератор: Модераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group