Забавы с шахматной доской (по мотивам китайской олимпиады)

[Ktina]

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

[arseniiv]

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

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

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

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

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

[12d3]

arseniiv в сообщении #1169660 писал(а):

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

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

[Yadryara]

Ktina в сообщении #1169647 писал(а):

идущих подряд по вертикали, горизонтали или диагонали,

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

[arseniiv]

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 --

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

[12d3]

arseniiv в сообщении #1169671 писал(а):

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

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

[Ktina]

Yadryara в сообщении #1169669 писал(а):

Ktina в сообщении #1169647 писал(а):

идущих подряд по вертикали, горизонтали или диагонали,

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

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

[12d3]

20 клеток для $n=4$

[arseniiv]

Красота!

[grizzly]

Вариант для 6-14. Просто передвинул пару клеток в решении arseniiv.


-- 17.11.2016, 23:17 --

Ещё чуть лучше. 6-12:

[grizzly]

Попытался нарисовать из соображений симметрии. Получилось 6-11:

Есть подозрение, что лучше уже никак.

-- 18.11.2016, 00:22 --

5-14. Теперь у меня всё.

[12d3]

grizzly в сообщении #1169790 писал(а):

Есть подозрение, что лучше уже никак.

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

[12d3]

5-12. Меньше не бывает.