12 королей

[Ktina]

Сколькими способами можно разместить 12 королей на доске $6\times 8$ так, чтобы они не били друг друга?

[Yadryara]

Кстати, а почему именно такое количество королей и такая доска?

А вариант с $n^2$ королями на доске площадью $4n^2$ рассматривался? Я попробовал на Бэйсике, получил странную последовательность: $1, 14, 459, ...$ Ну то есть нашёл $14$ уникальных способов расставить 4-х королей на доске $4\times 4$ и $459$ уникальных способов расставить 9-х королей на доске $6\times 6$.

В OEIS такой нету.

Задача хорошо переформулируется через "Морской бой".

[Yadryara]

В качестве ответа на заглавный вопрос темы предлагаю число $6533$.

Нашлось именно столько уникальных вариантов. Для прямоугольников их определять легче. Надо лишь исследовать поворот на $180^\circ$ и отражения от горизонтальных и вертикальных осей симметрии. То есть в прямоугольнике имеется до $3$-х копий каждого варианта расстановки. А в квадрате — до $7$ копий. Добавляются ещё повороты на $90^\circ$ и $270^\circ$, а также отражения от двух главных диагоналей.

Полученные результаты сведены в таблицу. Количество королей здесь везде максимальное, то есть $\frac{mn}4$.

\begin{tabular}{|l|r|r|r|r|r|r|r|r|r|r|r|c|} \hline \quad m \ \ \quad n \to$ & 2 &4&6&8&10&12&14&16&18\\ \hline \quad 2 & 1 & 4 & 8 & 22 & 48 & 116 & 256 & 584 & 1280\\ \hline \quad 4 & 4 & 14 & 106 & 473& 1939 & & & & \\ \hline \quad 6 & 8 & 106 & 459 & 6533& & & & & \\ \hline \end{tabular}

Построчных последовательностей в OEIS не обнаружено. Диагональной(для квадратов) — тоже. Разумеется, я не уверен в точности полученных результатов. Может быть, кто-то проверит и\или дополнит. Кстати, удивило, что задачей не заинтересовался никто из наших программеров.

Возможно после проверки стоит добавить в OEIS.

[Yadryara]

Так, ну с первой строчкой понятно. Здесь $n=2k$. Явная формула общего члена, видимо, такая

$$a(k)= (k+1)\cdot2^{k-2} + (1+(-1)^k)^{\frac{k}2-1}$$

Таким образом, для следующего прямоугольника $2\times20$ имеем $k=10$, тогда

$a(10)= (10+1)\cdot2^{10-2} + (1+(-1)^{10})^{\frac{10}2-1}=11\cdot2^8 + 2^4 = 2832 $

Что и подтвердил программный перебор.

[Yadryara]

Если же говорить не о количестве уникальных расстановок, а об их общeм количестве, то в OEIS есть 3 последовательности:

$2\times n$ — A001787

$4\times n$ — A061593

$6\times n$ — A061594

Соответственно, если в теме всё же спрашивается об общем количестве расстановок, то ответ на заглавный вопрос темы — $26040$

[Pphantom]

Тема перемещена из форума «Загадки, головоломки, ребусы» в форум «Олимпиадные задачи (М)»

[Yadryara]

Сейчас обсуждается добавление в OEIS 3-х последовательностей. Обозначения чуть другие. Для первых двух строк вышеприведённой таблицы:

Number of nonequivalent ways to place n nonattacking kings on a $2\times 2n$ chessboard under all symmetry operations of the rectangle — A322284; $4\times 2n$ — A321614.

Первые две строки заполнены:

\begin{tabular}{|l|r|r|r|r|r|r|r|r|r|r|r|c|} \hline \quad m \ \ \quad n \to$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\ \hline \quad 2 & 1 & 4 & 8 & 22 & 48 & 116 & 256 & 584 & 1280\\ \hline \quad 4 & 4 & 23 & 106 & 473& 1939 & 7618 & 28703 & 105112 & 375597\\ \hline \end{tabular}

Для второй строки Колин Баркер предложил неслабую формулу для $ n > 9 $.

$a_n = 12a_{n-1} - 54a_{n-2} + 98a_{n-3} + 17a_{n-4} - 346a_{n-5} + 505a_{n-6} - 210a_{n-7} - 120a_{n-8} + 126a_{n-9} - 27a_{n-10}$

Как заполнять третью строку я тоже теперь знаю.

Есть ещё отдельная последовательность для квадратных досок, но о ней позже.

[Yadryara]

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

Есть ещё отдельная последовательность для квадратных досок, но о ней позже.

Вчера утверждена — A319096. Там, в качестве примера, как раз приведены все $14$ расстановок для доски $4\times 4$.

Более ранние пока что не утверждены. Актуальная таблица нынче такая:

\begin{tabular}{|l|r|r|r|r|r|r|r|r|r|c|} \hline \quad Клеток & 2 & 4 & 6 & 8 & 10 & 12\\ \hline \quad 2 & \textcolor{magenta}{1} & 4 & 8 & 22 & 48 & 116\\ \hline \quad 4 & & \textcolor{magenta}{14} & 106 & 473& 1939 & 7618\\ \hline \quad 6 & & & \textcolor{magenta}{459}& 6533 & 41592 & 244276\\ \hline \quad 8 & & & & \textcolor{magenta}{35312} & 645386 & 5285227\\ \hline \quad 10 & & & & & \textcolor{magenta}{4072108} & \\ \hline \quad 12 & & & & & & \textcolor{magenta}{638653285}\\ \hline \end{tabular}

Пользоваться просто. Если надо узнать количество уникальных расстановок максимального количества не атакующих друг друга королей на доске формата $6\times 8$ смотрим на пересечение соответствующих строк и видим $6533$.

Фиолетовым отмечены числа как раз для квадратных досок. Если последовательность для прямоугольников, например для $4\times 2n$, то мне советовали обсчитывать только прямоугольные симметрии, хоть это и приводит к тому, что в одном единственном случае в каждой последовательности получается большее число. Для $4\times 4$ это не $14$ и не $79$, а $23$. Но уникальных вариантов всё же $14$, остальные — копии. Что и отражено в таблице.