Четыре подряд занятые клетки на доске

[gipokrat]

Какое минимальное число фишек надо взять, чтобы при любой их расстановке на клетках шахматной доски обязательно встретились бы 4 фишки, стоящие друг за другом по горизонтали, вертикали или диагонали?

[wrest]

Мне удалось расставить 44 так чтобы нигде небыло по 4 в ряд.

  a b c d e f g h
8 X X X . X X X . 8
7 X X X . X . X X 7
6 X X . X X X . X 6
5 . . . X . X X X 5
4 X X X . X X . . 4
3 X . X X . . X X 3
2 X X . X . X X X 2
1 . X X X . X X X 1
  a b c d e f g h

[gipokrat]

wrest
Спасибо! Да, эта расстановка даёт нижнюю оценку $M\ge 44$, где $M$ — максимальное число фишек, которые можно расставить на доске $8\times 8$ без появления четырёх подряд по горизонтали, вертикали или диагонали.

Тем самым она показывает, что $44$ фишки ещё не гарантируют появления нужной четвёрки. Следовательно, для исходного искомого числа $N$ имеем $N\ge 45$.

У меня вычислительно получается, что на самом деле $M=44$, то есть предполагаемый ответ на исходную задачу равен $N=M+1=45$.

Остаётся самая интересная часть: доказать верхнюю оценку $M\le 44$, то есть невозможность расстановки $45$ фишек без четырёх подряд. Компьютерная проверка это подтверждает, но хотелось бы понять, есть ли аккуратное ручное доказательство.

[wrest]

gipokrat в сообщении #1726780 писал(а):

но хотелось бы понять, есть ли аккуратное ручное доказательство.

Не выходит. Диагонали портят всю малину.

[wrest]

Посчитал тут задачу до стороны доски 16

N   N²    Максимум  Пустых  Плотность   ⌈2N²/3⌉  Разница
─────────────────────────────────────────────────────────
3    9       9        0     100.00%       6         +3
4   16      12        4      75.00%      11         +1
5   25      18        7      72.00%      17         +1
6   36      25       11      69.44%      24         +1
7   49      36       13      73.47%      33         +3
8   64      44       20      68.75%      43         +1
9   81      56       25      69.14%      54         +2
10 100      68       32      68.00%      67         +1
11 121      84       37      69.42%      81         +3
12 144      96       48      66.67%      96          0
13 169     113       56      66.86%     113          0
14 196     131       65      66.84%     131          0
15 225     152       73      67.56%     150         +2
16 256     172       84      67.19%     171         +1

Похоже на то что асимптотически максимальная плотность фишек будет куда-то сходиться, в район 2/3
Значения посчитаны с использованием sat-солвера, так что с большой долей вероятности (с корректировкой на возможно кривой код) это истинные максимумы по размещению фишек.

[wrest]

Вот, например, плитка 12х12, которая замощает плоскость с плотностью фишек 2/3

. * . * * * . * . * * *
. * * * . * . * * * . *
* . * . * * * . * . * *
* . * * * . * . * * * .
* * . * . * * * . * . *
. * . * * * . * . * * *
* * * . * . * * * . * .
* . * . * * * . * . * *
. * * * . * . * * * . *
* * . * . * * * . * . *
* . * * * . * . * * * .
* * * . * . * * * . * .

Она состоит из расположенных по диагонали трёх типов плиток 4х4, то есть каждого типа по три.
Это доказывает, что асимптотическая плотность 2/3, поскольку ранее доказано, что для одиночной плитки (доски) 12х12 максимальная плотность 2/3

[gipokrat]

wrest
Красивая плитка! По-моему, вывод про асимптотику $2/3$ верен, но две оценки стоит развести аккуратно, потому что держатся они на разных фактах.

Обозначим через $a(n)$ максимальное число фишек на доске $n\times n$ без четырёх подряд по горизонталям, вертикалям и диагоналям.

Верхняя оценка. Пусть сначала $n$ кратно $12$. Разобьём доску на блоки $12\times12$. В каждом блоке не больше $a(12)$ фишек, так как четвёрка внутри блока была бы четвёркой и на всей доске. Поэтому $a(n)\le a(12)\cdot(n/12)^2$. Если $a(12)\le96$, то получаем $a(n)\le \frac23n^2$ для всех $n$, кратных $12$.

Для произвольного $n$ положим $m=12\lceil n/12\rceil$. Любая допустимая расстановка на доске $n\times n$ остаётся допустимой на доске $m\times m$, поэтому $a(n)\le a(m)$. Так как $m$ кратно $12$, имеем $a(m)\le \frac23m^2$. Следовательно,
$a(n)\le \frac23m^2=\frac23n^2+O(n)$.
Здесь существенно, что оценка $a(12)\le96$ пока получается вычислительно.

Нижняя оценка. Её даёт именно Ваша периодическая плитка, а не сама по себе оптимальность одиночной доски $12\times12$. Если рассматривать эту плитку как конфигурацию на торе $12\times12$ и на торе нет четырёх подряд, то периодическое замощение плоскости тоже не содержит четырёх подряд.

Этого достаточно: длина четвёрки меньше периода плитки, поэтому четыре подряд в замощении — в любом направлении, включая четвёрки, пересекающие границы соседних копий, — это в точности четыре подряд на торе $12\times12$, и обратно. Значит проверка на торе равносильна проверке всего бесконечного замощения.

Тогда из периодического замощения можно вырезать квадрат $n\times n$ с $\frac23n^2-O(n)$ занятыми клетками. Следовательно, $a(n)\ge \frac23n^2-O(n)$.

Итак, вместе верхняя и нижняя оценки дают
$a(n)=\frac23n^2+O(n)$,
а значит
$\lim\limits_{n\to\infty}\frac{a(n)}{n^2}=\frac23$.

[wrest]

gipokrat в сообщении #1726890 писал(а):

Нижняя оценка. Её даёт именно Ваша периодическая плитка, а не сама по себе оптимальность одиночной доски $12\times12$. Если рассматривать эту плитку как конфигурацию на торе $12\times12$ и на торе нет четырёх подряд, то периодическое замощение плоскости тоже не содержит четырёх подряд.

Насчёт тора не понял, но
1. Максимум что можно уложить в доску 12х12 это 2/3 (это доказано вычислительно)
2. Существует замощающая плоскость плитка 12х12 с плотностью 2/3 (предъявлено явно)
Два этих факта дают предел при размере квадратной доски, стремящемся в бесконечность, равный 2/3

[gipokrat]

wrest
Да, именно это я и имел в виду.

Про тор я сказал только как про формализацию периодического повторения блока $12\times12$: координаты считаются по модулю $12$, и тем самым отдельно проверяются в том числе четвёрки, пересекающие границы соседних копий блока. Если замощающая плитка уже предъявлена явно и проверено, что при её периодическом повторении четвёрок не возникает, то слово «тор» можно вообще не использовать.

Согласен, для предела нужны ровно два факта:

1. $a(12)\le 96$ — верхняя оценка, полученная вычислительно.

2. Существует периодическая конфигурация периода $12\times12$ с плотностью $2/3$, не содержащая четырёх подряд.

Тогда действительно получается
$a(n)=\frac23 n^2+O(n)$,
откуда
$\lim\limits_{n\to\infty}\frac{a(n)}{n^2}=\frac23$.