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

задан 6 Ноя 12:23

1

А дустом вы @falcao не пробовали?

(6 Ноя 12:25) knop
1

http://oeis.org/A018807 для квадратных досок

(6 Ноя 14:59) knop
2

http://oeis.org/A061594 для досок 6x2n

(6 Ноя 15:00) knop
1

Отдельно, как всегда, меня интересует смысл меток "2011_год" и "матбой".

(6 Ноя 15:03) knop

@knop, матбой 2011г. И чизкейк.

(7 Ноя 0:32) Казвертеночка
1

@Казвертеночка, а что за матбой-то? Какой турнир, какой класс, какая там лига?

(7 Ноя 8:44) knop

@knop, обычный матбой, не помню, с какого турнира, мне по почте прислали, мопед не мой и шапка не моя.

(7 Ноя 13:07) Казвертеночка
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
2

Хотя ответ здесь "красивый", а именно, 3600, согласно ссылкам от @knop, но его, скорее всего, трудно получить совсем уж вручную. Попробую вкратце описать общую технику, позволяющую ответить на этот вопрос. Прежде всего, разобьём доску на квадратики 2x2, из из которых составлена новая доска 3x4. Ясно, что в пределах одного квадратика 2x2 король может находиться только один. Поскольку новых клеток стало 12, то и королей получается не более 12. Значит, в каждом "большом" квадрате должен быть ровно один король.

Далее опишем, как эту переформулированную задачу можно решить для случая доски 3xn из "больших" клеток. Имеется конечное число способов расположения трёх королей в первом столбце. Каждому из них соответствует свой вариант расстановки королей во 2-м столбце исходной доски 6x(2n). От этого варианта зависит то, как можно продолжать конфигурацию вправо. Если не ошибаюсь, с точностью до симметрии имеется 12 вариантов расположения королей в указанном 2-м столбце (их там от 0 до 3). Для каждого такого варианта рассматриваем последовательности x(n), y(n), ... , z(n) (то есть тут их будет 12), и каждая из них даёт конечное число продолжений, в результате чего эти последовательности рекуррентно (линейно) выражаются через x(n-1), y(n-1), ... , z(n-1). Далее эта сложная система решается (скажем, на компьютере), и получается общая формула. Судя по виду той формулы, которая дана по ссылке, она не должна возникать в результате чего-то совсем уж простого. Общий подход видится примерно таким, разве что где-то могут быть технические упрощения.

ссылка

отвечен 6 Ноя 22:49

@falcao, большое спасибо! Только не 3600, а 26040, но это несущественно.

(7 Ноя 0:32) Казвертеночка
1

@Казвертеночка: да, верно. Я думал, что тут нумерация идёт с единицы, а оказалось, что с нуля. Значит, реальное число ещё больше, что делает сомнительным простые способы получения ответа.

А вот над появлением 3600 для доски 6x6, надо будет подумать, нет ли здесь какого-то лёгкого решения?

(7 Ноя 1:45) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,005
×795
×19
×13
×2

задан
6 Ноя 12:23

показан
79 раз

обновлен
7 Ноя 14:53

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru