2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 12 королей
Сообщение06.11.2018, 11:25 
Аватара пользователя


01/12/11

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

 Профиль  
                  
 
 Re: 12 королей
Сообщение24.11.2018, 01:02 
Аватара пользователя


29/04/13
7126
Богородский
Кстати, а почему именно такое количество королей и такая доска?

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

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

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

 Профиль  
                  
 
 Re: 12 королей
Сообщение01.12.2018, 09:58 
Аватара пользователя


29/04/13
7126
Богородский
В качестве ответа на заглавный вопрос темы предлагаю число $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.

 Профиль  
                  
 
 Re: 12 королей
Сообщение02.12.2018, 06:20 
Аватара пользователя


29/04/13
7126
Богородский
Так, ну с первой строчкой понятно. Здесь $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 $

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

 Профиль  
                  
 
 Re: 12 королей
Сообщение02.12.2018, 07:41 
Аватара пользователя


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

$2\times n$A001787

$4\times n$A061593

$6\times n$A061594

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

 Профиль  
                  
 
 Posted automatically
Сообщение02.12.2018, 12:12 
Заслуженный участник


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

 Профиль  
                  
 
 Re: 12 королей
Сообщение23.12.2018, 07:26 
Аватара пользователя


29/04/13
7126
Богородский
Сейчас обсуждается добавление в 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}$

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

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

 Профиль  
                  
 
 Re: 12 королей
Сообщение25.12.2018, 11:54 
Аватара пользователя


29/04/13
7126
Богородский
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$, остальные — копии. Что и отражено в таблице.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group