Расставить шашки так, чтобы каждая была под боем

[Ktina]

Какое максимальное число шашек можно расставить на доске $9\times 9$ так, чтобы каждая была под боем?

[hippie]

Шашки ставятся только на чёрные поля? Тогда 20.

[iancaple]

А если на белые (которых 40, т.к.поле a1 принято считать черным), то тоже 20

[Skeptic]

Сколько одноцветных полей, столько шашек можно расставить.

[NSKuber]

Skeptic
Вам знакомы правила шашек? Если вы поставите три шашки подряд по диагонали, то среднюю никакая из двух крайних бить не будет. Если вы все белые поля заставите шашками, никто никого бить не будет.

[Ktina]

hippie в сообщении #1066408 писал(а):

Шашки ставятся только на чёрные поля? Тогда 20.

Можно на любые поля.

[grizzly]

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

Можно на любые поля.

И что, очевидно данные выше ответы "40" разве не верны?

[Ktina]

grizzly
Ну, как бы, верны, только без доказательства того, что 41 нельзя, смотрятся как-то блекловато.

[iancaple]

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

grizzly
Ну, как бы, верны, только без доказательства того, что 41 нельзя, смотрятся как-то блекловато.

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

Ясно, что на край доски нельзя. Надо показать, что еще 4 поля будут не заняты. Выделим 4 непересекающихся множества, каждое из которых не может быть занято полностью.

[NSKuber]

Общее решение:
Очевидно, на край доски ставить нельзя.
Посчитаем максимум для чёрных клеток. Разобьём внутренний квадрат $7\times 7$ на пять частей (4 красных и одна зелёная на рисунке). В каждой - по пять чёрных клеток.

Ясно, что в красные квадраты по пять шашек на чёрные клетки поставить нельзя, так как тогда центральную никто не бьёт. Предположим, что мы смогли расставить больше двадцати шашек на чёрные. Тогда, по принципу Дирихле, как минимум в одной из пяти частей их больше четырёх. По только что упомянутому, пять их может быть только в зелёном кресте, в красных квадратах тогда по 4 шашки, а всего - 21. Значит, в центра $C$ есть шашка. Её должен бить кто-то из соседей, пусть, без ограничения общности, шашка в клетке 1. Так как все чёрные клетки зелёного креста заполнены шашками, шашку 1 обязана бить центральная, значит в клетке 2 пусто, а тогда шашку 3 (помним, что в красных квадратах по 4 шашки) никто не бьёт, противоречие. То есть на чёрные больше 20 не расставить.

С белыми ещё проще: выделим во внутреннем квадрате 4 области (цветные на рисунке), в каждой из которых по 6 белых клеток, и все белые клетки внутреннего квадрата содержатся в их объединении.

Очевидно, в каждой из областей можно поставить не более пяти шашек на белые клетки, значит всего - не более двадцати.

[Ktina]

Вот теперь всем спасибо!
Любопытно было бы также обобщить задачу до доски $n\times n$. Например, при $n=8$, сиречь на классической доске, задача решается удивительно легко.

[mserg]

до 35x35 оптимум достаточно легко находится с помощью линейного программирования.

для общего случая можно заметить, что максимальная "плотность упаковки" составляет 4/5. Т.е. ориентировочно максимум будет $\frac{4}{5}(n-2)^2$

на "больших" n "визуально" оптимум достигался на "плотной упаковке" в центре с некоторыми возмущениями по краям.