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

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




Новая тема Ответить На страницу 1, 2  След.
 Несколько ферзей, чтобы каждый бил ровно двух из остальных


09/07/11
103
Требуется поставить на доску несколько ферзей так, чтобы каждый бил ровно двух из остальных. Для какого количества ферзей это можно сделать? Найдите все возможные варианты. Под доской подразумевается обычная шахматная доска.

Профиль
 Re: Несколько ферзей, чтобы каждый бил ровно двух из остальных
Аватара пользователя


01/11/14
2231
Principality of Galilee
gipokrat в сообщении #1721262 писал(а):
Для какого количества ферзей это можно сделать?
Вы имеете в виду максимальное количество ферзей?
Минимальное количество — 3, например, так:

Изображение

Профиль
 Re: Несколько ферзей, чтобы каждый бил ровно двух из остальных
Заслуженный участник
Аватара пользователя


13/08/08
14678
Раскраска доски в данной задаче не актуальна, так что вспоминаю рисование и представляю вариант с четырьмя ферзями, которые изображены чёрными кружками (ударение на а).
$\begin{picture}(320,320)
\multiput(0,0)(0,40){9}%
{\line(1,0){320}}
\multiput(0,0)(40,0){9}%
{\line(0,1){320}}
\put(20,20){\circle*{20}}
\put(300,20){\circle*{20}}
\put(300,300){\circle*{20}}
\put(300,260){\circle*{20}}
\end{picture}$

Профиль
 Re: Несколько ферзей, чтобы каждый бил ровно двух из остальных


09/07/11
103
Gagarin1968 в сообщении #1721266 писал(а):
gipokrat в сообщении #1721262 писал(а):
Для какого количества ферзей это можно сделать?
Вы имеете в виду максимальное количество ферзей?

Условие гласит: "Найдите все возможные варианты." Подсказка: их много, как колен (если не считать пустой расстановки).

Профиль
 Re: Несколько ферзей, чтобы каждый бил ровно двух из остальных
Аватара пользователя


28/11/22
81
Можно дополнить до 9-ти ферзей и, соответственно до 6-ти вариантов расположения.

$\begin{picture}(320,320)
\multiput(0,0)(0,40){9}%
{\line(1,0){320}}
\multiput(0,0)(40,0){9}%
{\line(0,1){320}}
\put(20,20){\circle*{20}}
\put(60,60){\circle*{20}}
\put(100,100){\circle*{20}}
\put(140,140){\circle*{20}}
\put(180,180){\circle*{20}}
\put(220,220){\circle*{20}}
\put(260,260){\circle*{20}}
\put(300,300){\circle*{20}}
\put(20,300){\circle*{20}}
\end{picture}$

gris, украл у Вас идею и разметку :oops:

Профиль
 Re: Несколько ферзей, чтобы каждый бил ровно двух из остальных
Аватара пользователя


01/11/14
2231
Principality of Galilee
gipokrat в сообщении #1721283 писал(а):
Условие гласит: "Найдите все возможные варианты." Подсказка: их много, как колен
Ну, во-первых, колен всего 12, и это Вам хорошо известно.
Во-вторых, как мне кажется, задача недоформулирована. Ваше условие (из стартового поста) гласит:
gipokrat в сообщении #1721262 писал(а):
Для какого количества ферзей это можно сделать?
Скорее всего, здесь пропущено слово "максимального".
Потому что это можно сделать для трёх (меньше нельзя), четырёх, пяти и т.д. ферзей.
После нескольких проб мне удалось расставить 12 ферзей:

Изображение

И я не уверен, что нельзя больше. Попробую отыскать.

Профиль
 Re: Несколько ферзей, чтобы каждый бил ровно двух из остальных
Аватара пользователя


01/11/14
2231
Principality of Galilee
Есть, нашёл расстановку из 13 ферзей!

Изображение

И я по-прежнему не уверен, что это максимум.

Профиль
 Re: Несколько ферзей, чтобы каждый бил ровно двух из остальных
Заслуженный участник
Аватара пользователя


16/07/14
10987
Цюрих
Вложение:
download (2).png
download (2).png [ 18.76 Кб | Просмотров: 0 ]
ortools нашло расстановку из 14
Оптимальность пока не доказало.

Профиль
 Re: Несколько ферзей, чтобы каждый бил ровно двух из остальных


14/01/11
3722
mihaild в сообщении #1721292 писал(а):
ortools нашло расстановку из 14

Я так понимаю, ortools сводит задачу к формату, который может переварить какой-нибудь известный решатель вроде CPLEX, GLPK и т.д. Вы какой использовали?

Профиль
 Re: Несколько ферзей, чтобы каждый бил ровно двух из остальных


27/08/16
14019
gipokrat в сообщении #1721262 писал(а):
Найдите все возможные варианты.
С точностью до симметрий?

Профиль
 Re: Несколько ферзей, чтобы каждый бил ровно двух из остальных
Заслуженный участник
Аватара пользователя


16/07/14
10987
Цюрих
Sender в сообщении #1721293 писал(а):
Я так понимаю, ortools сводит задачу к формату, который может переварить какой-нибудь известный решатель вроде CPLEX, GLPK и т.д.
Она обертка над разными решателями. Я брал CpModel, не знаю точно, что внутри, вроде бы что-то своё.

Профиль
 Re: Несколько ферзей, чтобы каждый бил ровно двух из остальных
Аватара пользователя


11/12/16
16406
уездный город Н
mihaild в сообщении #1721292 писал(а):
Оптимальность пока не доказало.


Ограничение сверху - 15, при этом должны быть заняты три угла.
Если заняты только два угла, то ограничение сверху - 14.

UPD: Но не доказано :roll:

Профиль
 Re: Несколько ферзей, чтобы каждый бил ровно двух из остальных


09/07/11
103
realeugene в сообщении #1721296 писал(а):
gipokrat в сообщении #1721262 писал(а):
Найдите все возможные варианты.
С точностью до симметрий?

В задаче спрашивается, сколько может быть ферзей. И требуется найти все возможные варианты этого количества.
Gagarin1968, это и Вам ответ.

Профиль
 Re: Несколько ферзей, чтобы каждый бил ровно двух из остальных
Аватара пользователя


01/11/14
2231
Principality of Galilee
EUgeneUS в сообщении #1721316 писал(а):
Ограничение сверху - 15, при этом должны быть заняты три угла.
EUgeneUS
Можете показать такую расстановку?
У меня больше 14 не получается. Всегда остаётся по меньшей мере один ферзь, бьющий трёх сородичей.

Профиль
 Re: Несколько ферзей, чтобы каждый бил ровно двух из остальных
Аватара пользователя


11/12/16
16406
уездный город Н
Gagarin1968 в сообщении #1721323 писал(а):
Можете показать такую расстановку?


Нет, и скорее всего её не существует.

Был план оценить верхнюю границу через подсчет "занятых" горизонталей, вертикалей и диагоналей. А потом доказать, что три угла не могут быть заняты.
Но нашел ошибку в рассуждениях ещё на первом шаге.

Профиль
Показать сообщения за:  Поле сортировки  
Новая тема Ответить  [ Сообщений: 21 ]  На страницу 1, 2  След.

Модератор: Модераторы



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

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



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