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

[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$.

[wrest]

Я попробовал посчитать обобщённую задачу "нет k в ряд на плоскости" (тут рассматривалось k=4), и оказалось, что максимальрая плотность покрытия фишками при k=5 и k=6 одна и та же и равна 4/5, хотя для k=5 ожидалось что плотность будет 5/6
То есть замостить плоскость так, чтобы не было 5 фишек подряд, можно с плотностью фишек 4/5 и это же самое замощение подходит для задачи "не более 6 фишек подряд".
Такая же картина проявляется для k=7 и k=8, похоже что для них максимальная плотность при замощении плоскости равна 6/7, хотя для k=8 ожидалось 7/8

[gipokrat]

wrest в сообщении #1727435 писал(а):

Я попробовал посчитать обобщённую задачу "нет k в ряд на плоскости" (тут рассматривалось k=4), и оказалось, что максимальрая плотность покрытия фишками при k=5 и k=6 одна и та же и равна 4/5, хотя для k=5 ожидалось что плотность будет 5/6
То есть замостить плоскость так, чтобы не было 5 фишек подряд, можно с плотностью фишек 4/5 и это же самое замощение подходит для задачи "не более 6 фишек подряд".
Такая же картина проявляется для k=7 и k=8, похоже что для них максимальная плотность при замощении плоскости равна 6/7, хотя для k=8 ожидалось 7/8

Очень интересно. Я бы только уточнил обозначения.

Пусть $a_r(n)$ — максимальное число фишек на доске $n\times n$ без $r$ подряд по горизонталям, вертикалям и диагоналям, а $\rho_r$ — соответствующая предельная плотность, если предел существует.

Тогда уже по одной строке имеем тривиальную верхнюю оценку
$\rho_r\le \frac{r-1}{r}$,
потому что в каждом отрезке длины $r$ должна быть хотя бы одна пустая клетка.

Поэтому для запрета $5$ подряд плотность $5/6$ невозможна уже из строк: верхняя оценка там $4/5$. Видимо, ожидание $5/6$ относится к запрету $6$ подряд.

Если я правильно понимаю Ваши вычисления, получается такая картина:
$\rho_4=2/3$,
$\rho_5=\rho_6=4/5$,
$\rho_7=\rho_8=6/7$.

То есть самое неожиданное не то, что для запрета $5$ подряд получается $4/5$, а то, что для запрета $6$ подряд плотность, похоже, всё равно остаётся $4/5$, хотя строковая оценка разрешала бы $5/6$. Аналогично для запрета $8$ подряд: строковая оценка даёт $7/8$, а вычислительно получается $6/7$.

Похоже на эффект чётности: для проверенных значений
$\rho_r=\frac{2\lceil r/2\rceil-2}{2\lceil r/2\rceil-1}$.
То есть запреты $2m-1$ подряд и $2m$ подряд дают одну и ту же плотность
$\frac{2m-2}{2m-1}$.

Если это действительно сохраняется дальше, то главная нетривиальная часть — верхняя оценка для чётных длин запрета: почему запрет $2m$ подряд уже вынуждает ту же плотность, что и более сильный запрет $2m-1$ подряд.

[wrest]

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

То есть самое неожиданное не то, что для запрета $5$ подряд получается $4/5$, а то, что для запрета $6$ подряд плотность, похоже, всё равно остаётся $4/5$, хотя строковая оценка разрешала бы $5/6$. Аналогично для запрета $8$ подряд: строковая оценка даёт $7/8$, а вычислительно получается $6/7$.

Да, именно это неожиданно.

-- добавлено через 2 минуты --

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

Похоже на эффект чётности: для проверенных значений

Да, но только для них. Дальше надо проверять, а это тяжко
Вдруг они начнут группироваться по три подряд, или перестанут группироваться. Непонятно.

[wrest]

Вот например замощающая плоскость плитка 5x5 для "нельзя 5 в ряд" и "нельзя 6 в ряд" с плотностью фишек 4/5

# # . # #
# # # # .
# . # # #
# # # . #
. # # # #

А вот для "нельзя 4 в ряд" потребовалась плитка 12х12