2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Забавы с шахматной доской (по мотивам китайской олимпиады)
Сообщение17.11.2016, 11:20 
Аватара пользователя


01/12/11

8634
Для каждого $n\in\{1, 2, 3, 4, 5, 6, 7, 8\}$ найти, какое минимальное количество клеток надо отметить на шахматной доске, чтобы среди любых $n$ клеток, идущих подряд по вертикали, горизонтали или диагонали, была хотя бы одна отмеченная.

 Профиль  
                  
 
 Re: Забавы с шахматной доской (по мотивам китайской олимпиады)
Сообщение17.11.2016, 12:48 
Заслуженный участник


27/04/09
28128
Ощущение déjà vu (прямоугольники $2\times3$).

Закроем сразу очевидные крайние случаи, чтобы другим их не писать. Для 1 это вся доска → 64, для 8 это матрица почти любой перестановки множества $1..8$ (для удобства можно сразу зафиксировать две клетки, принадлежащие диагоналям) → 8; если меньше, одна из горизонталей/вертикалей окажется пустой.

2: надо упаковать неотмеченные клетки поближе, чтобы они при этом не соседствовали по диагонали, вертикали и горизонтали. Это можно сделать несколькими способами, но в любом случае в каждом квадрате $2\times2$ будет не больше одной по построению. Этот максимум достижим, если распространить «уголок» такого же размера на всю доску периодически. → 48.

-- Чт ноя 17, 2016 15:08:54 --

Для 7 у меня получилось 9, но внятно объяснить принцип построения и доказать, что не может быть 8, не возьмусь. Рисунок:

Изображение

 Профиль  
                  
 
 Re: Забавы с шахматной доской (по мотивам китайской олимпиады)
Сообщение17.11.2016, 13:25 
Заслуженный участник


04/03/09
906
arseniiv в сообщении #1169660 писал(а):
Для 7 у меня получилось 9, но внятно объяснить принцип построения и доказать, что не может быть 8, не возьмусь

Если бы было можно обойтись 8 клетками, то в каждой вертикали будет по одной клетке, причем это не самая верхняя и не самая нижняя клетка. Но тогда две горизонтали окажутся пустыми.

 Профиль  
                  
 
 Re: Забавы с шахматной доской (по мотивам китайской олимпиады)
Сообщение17.11.2016, 13:52 
Аватара пользователя


29/04/13
7083
Богородский
Ktina в сообщении #1169647 писал(а):
идущих подряд по вертикали, горизонтали или диагонали,

Кстати, не уточняется, что имеются в виду только главные диагонали.

 Профиль  
                  
 
 Re: Забавы с шахматной доской (по мотивам китайской олимпиады)
Сообщение17.11.2016, 14:01 
Заслуженный участник


27/04/09
28128
12d3
Спасибо, это примерно то, как я думал. :-)

Теперь берёмся за 3. Тут снова можно делать как для 2 — нарисовать область из свободных клеток побольше и паковать их. Лучшее, чего я добился (28) — это

Изображение

Понятно, что в каждой строке и каждом столбце должно быть закрашено минимум две клетки, и находиться эти закрашенные клетки должны жёстко как на рисунке. Понятно, что после этого закрашивания нельзя освободить клетки по диагонали от свободных. Только как полное обоснование это для меня не выглядит почему-то, как будто забыл что-то.

Yadryara в сообщении #1169669 писал(а):
Кстати, не уточняется, что имеются в виду только главные диагонали.
Тоже так понял, что любые диагонали.

-- Чт ноя 17, 2016 16:23:07 --

4. Из периодических структур лучшей вышла та, что справа, а квадраты уже уступают:

Изображение

Опять без обоснований.

-- Чт ноя 17, 2016 16:55:45 --

Накидать ещё необоснованных кандидатов для 6?

Изображение

(правый более-менее разумно выглядит, хотя и отстаёт от левого на 1).

-- Чт ноя 17, 2016 16:56:10 --

И на этом от меня пока всё.

-- Чт ноя 17, 2016 16:57:43 --

Нет, не всё. Левый кандидат и вовсе не кандидат, в нём ошибка на большей побочной диагонали.

 Профиль  
                  
 
 Re: Забавы с шахматной доской (по мотивам китайской олимпиады)
Сообщение17.11.2016, 15:54 
Заслуженный участник


04/03/09
906
arseniiv в сообщении #1169671 писал(а):
Теперь берёмся за 3. Тут снова можно делать как для 2 — нарисовать область из свободных клеток побольше и паковать их. Лучшее, чего я добился (28) — это

И эта раскраска оптимальна. Небольшим перебором можно получить, что 6 клеток на квадрат $4 \times 4$ не хватает, а значит на всю доску нужно 28 клеток.
Более того, это единственная оптимальная раскраска.

 Профиль  
                  
 
 Re: Забавы с шахматной доской (по мотивам китайской олимпиады)
Сообщение17.11.2016, 16:38 
Аватара пользователя


01/12/11

8634
Yadryara в сообщении #1169669 писал(а):
Ktina в сообщении #1169647 писал(а):
идущих подряд по вертикали, горизонтали или диагонали,

Кстати, не уточняется, что имеются в виду только главные диагонали.

Не уточняется, поскольку это не так :mrgreen:

 Профиль  
                  
 
 Re: Забавы с шахматной доской (по мотивам китайской олимпиады)
Сообщение17.11.2016, 17:09 
Заслуженный участник


04/03/09
906
20 клеток для $n=4$
Изображение

 Профиль  
                  
 
 Re: Забавы с шахматной доской (по мотивам китайской олимпиады)
Сообщение17.11.2016, 17:45 
Заслуженный участник


27/04/09
28128
Красота!

 Профиль  
                  
 
 Re: Забавы с шахматной доской (по мотивам китайской олимпиады)
Сообщение17.11.2016, 22:54 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Вариант для 6-14. Просто передвинул пару клеток в решении arseniiv.
Изображение

-- 17.11.2016, 23:17 --

Ещё чуть лучше. 6-12:
Изображение

 Профиль  
                  
 
 Re: Забавы с шахматной доской (по мотивам китайской олимпиады)
Сообщение17.11.2016, 23:55 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Попытался нарисовать из соображений симметрии. Получилось 6-11:
Изображение
Есть подозрение, что лучше уже никак.

-- 18.11.2016, 00:22 --

5-14. Теперь у меня всё.
Изображение

 Профиль  
                  
 
 Re: Забавы с шахматной доской (по мотивам китайской олимпиады)
Сообщение18.11.2016, 13:13 
Заслуженный участник


04/03/09
906
grizzly в сообщении #1169790 писал(а):
Есть подозрение, что лучше уже никак.

Это 100%, но доказательство длинное и корявое.
Остаются под вопросом только 4 и 5. 4-18 точно нельзя, а вот с 4-19 пока непонятно.

 Профиль  
                  
 
 Re: Забавы с шахматной доской (по мотивам китайской олимпиады)
Сообщение18.11.2016, 14:23 
Заслуженный участник


04/03/09
906
5-12. Меньше не бывает.
Изображение

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

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

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