Главное меню

Новости:

SMF - Just Installed!

Как расставить 14 ферзей на доске?

Автор Uscel, Март 14, 2024, 23:35

« назад - далее »

Uscel

Задача звучит так:
Какое максимальное количество ферзей можно расставить на обычной шахматной доске 8*8 так, чтобы каждый ферзь бил ровно двух других?
Я знаю, что правильный ответ: 14.
Внимание, вопрос: приведите хотя бы одну расстановку?
Дополнительный вопрос: сколько всего решений с 14 ферзями?
Внимание! Не путайте эту задачу со знаменитой задачей о расстановке 8 ферзей так, чтобы они не били друг друга!
Я в Интернете смог найти обсуждение только этой задачи, но она мне не нужна.

Стрым

Прочитав задачу и только приступив к осмыслению сразу возник вопрос. Что понимать по бьет другого? Поставим, например 2 ферзя в линию. Понятно, что они бьют друг друга. Теперь поставим в эту линию третьего ферзя. И вот тут становится непонятно: бьют или не бьют друг друга ферзи стоящие через фигуру на одной линии?
1 вариант.
С одной стороны: вроде как не бьют, поскольку между ними помеха (фигура)
2 Вариант.
С другой стороны: это же не шахматная партия, а математическая задача и там как правило считается, что фигура простреливает всю линию.
Я все же пытался решать вторым вариантом, он мне показался более интересным. Но более 11 ферзей у меня не получилось расставить.
Доказательство приводить не буду, но пример приведу.
Смотрим рисунок
  Но в условии сказано, что 14 должно быть. А при таком варианте 14 не получить точно. Я ждал, что кто то предложит вариант. Интересно было.
Наверное все же подразумевался 1-й вариант. Запустил поиск и нашел похожее условие, но в нем четко оговаривается:
Правда там условие отличалось:
Какое наибольшее количество ферзей можно поставить на шахматную доску так, чтобы каждый из них бил не более двух других (Фигуры не бьют друг сквозь друга.)?
И тут уже будет 14 ферзей. Пример расстановки смотрим на рисунке:
 Как видим несколько ферзей бьют меньше 2. (4 ферзя бьют по 1 фигуре и 10 по двум фигурам)
Но автор просит, что каждый ферзь бил ровно двух. Ну и примем во внимание замечание, что сквозь друг друга не бьют)
И вот тут у меня подозрение, что решения нет для 14 ферзей.
Но давайте сначала докажем, что 15 быть не может.
Каждый ферзь бьет в 8 направлениях. В двух направлениях должны стоять другие фигуры. Остается 6 направлений свободными и они уйдут за пределы доски.
Если удастся расставить 15 ферзей таким образом, то 15•6 = 90 направлений (линий) будут уходить за пределы доски.
А сколько всего на шахматной доске 8х8 направлений (линий) уходящих за пределы доски.
8 горизонталей в 2стороны = 16
8 вертикалей в 2 стороны = 16
15 диагоналей в 2 стороны + 15 перпендикулярных диагоналей в 2 стороны = 60
Итого 92 направления.
В 4 углах ферзи стоять не могут иначе будут бить больше двух. Значит 1 угол точно свободный. И тогда 2 направления из этого угла не используются ферзями.
Если будут заняты только 2 угла, то 3-й угол вычеркнет еще 2 направления.
Если же заняты 3 угла, то двойная диагональ не может быт занята. И это вычеркнет так же 2 направления.
Смотрим рисунок для понимания
В итоге получим, что направлений 92 - 2 - 2 = 88. А 15 ферзей должны дать больше. 90 направлений.
Не хватает. Значит невозможно.
Вообще аналогичными рассуждениями можно понять, что 3 угла не могут быть заняты и для 14 ферзей. Так как остальные 3 двойные диагонали так же не могут быть заняты и это вычеркнет ещё 6 направлений: 88 - 6 = 82 направления. А для 14 ферзей должно быть 14•6 =  84 направления. Не меньше.
И вот тут у меня гипотеза, что то похожее, когда шахматную доску без двух диагональных угловых клеток невозможно полностью замостить прямоугольниками на 2 клетки. Хотя вроде количество клеток четно. Так и тут предполагаю, что при строгом требовании бить ровно 2 фигуры, 14 ферзей не расставить.
У меня получилось расставить 12 ферзей.
14 не получилось, но и доказать невозможность не получается.
Привожу пример для 12.
    Интересно, если будет решение для 14