Расставляем слонов

[Ktina]

Пусть $x$ – количество всевозможных способов расставить слонов на шахматной доске так, чтобы никакие два из них не били друг друга (при этом хотя бы один слон должен стоять на доске). Докажите, что число $x+1$ является квадратом некоторого натурального числа.

[Mihr]

Что-то я недопонял. Если имеется лишь один слон, то можно его поставить на доску 64 способами. И бить ему при этом банально некого. Значит, в этом случае $x=64$, соответственно, $x+1=65$. Но 65 - это не квадрат.
Я неправильно понял условие? Или есть более сильное ограничение на количество слонов, чем "хотя бы один"?

[Ktina]

Mihr
Имеется в виду общее число способов, а не для какого-то конкретного количества слонов.

[Mihr]

То есть, число слонов не фиксировано? Вообще-то, желательно это оговаривать явно.
Но так тоже не получится, мне кажется. Пусть $y$ - число способов решения задачи только для чернопольных слонов. Тогда столько же, а именно $y$ способов расставить и белопольных. Общее число способов расставить слонов согласно комбинаторному правилу произведения получается $x=y^2$, но никак не $y^2+1$.

[Mikhail_K]

Mihr в сообщении #1420822 писал(а):

Общее число способов расставить слонов согласно комбинаторному правилу произведения получается $x=y^2$, но никак не $y^2+1$.

Итак, Вы любую расстановку слонов делите на две компоненты: белопольную (содержащую только тех слонов, которые на белых полях) и, соответственно, чернопольную.
Если $y$ - количество всевозможных белопольных компонент и оно же - количество всевозможных чернопольных, тогда, говорите Вы, $x=y^2$.
Но здесь надо учитывать, что одна из этих компонент может быть пустой. Если в расстановке все слоны стоят на чёрных полях и все на белых. То есть один из этих $y$ вариантов - это пустой вариант.
Видимо, Ktina не считает пустую доску (когда обе компоненты расстановки пусты, и на доске нет ни одного слона вообще) допустимой расстановкой. Вот и получается, что $x=y^2-1$, а не $x=y^2$.

[Booker48]

Mihr
О, как раз теперь всё получается. Надо только к полученному $x=y^2$ добавить $y$ позиций, когда на доске нет чернопольных слонов. И $y$ позиций, когда нет белопольных.

-- 15.10.2019, 09:52 --

Mikhail_K
И тогда получится $x=y^2+2y$. Пустая доска не считается, это в условии оговорено.

[Mikhail_K]

Booker48
Ну, это зависит от того, включать ли пустую доску в число возможных однопольных расстановок слонов. Я её включаю (так как это вполне возможная однопольная компонента допустимой непустой расстановки), Вы не включаете. То есть моё $y$ - это Ваше $y+1$. При этом, $x$ у нас одинаковое: $x=y^2-1$ у меня, $x=(y+1)^2-1$ у Вас, то есть мы оба не включаем пустую доску в итоговое число $x$.

Так что это не более чем вопрос обозначений.

[Mihr]

Mikhail_K, Booker48,
да, я невнимателен

[Booker48]

Mikhail_K в сообщении #1420835 писал(а):

Так что это не более чем вопрос обозначений.

Да, осознал, спасибо.

[Mihr]

Дорогие коллеги, а никто не попробовал посчитать само число $x$? (Без компьютера, разумеется).

[arseniiv]

Казалось бы, можно как с ладьями, но удаление полей под боем слона и самим слоном оставляет от полудоски полудоску не совсем прямоугольной формы. Это можно как-то удобно учесть?

-- Чт окт 17, 2019 03:38:34 --

[Booker48]

Как следует из предыдущего обсуждения, считать надо только белопольных слонов.
Минимальное количество таких слонов на доске - 1. И 32 варианта его расстановки.
Максимальное количество - 7. И, вроде бы, только 1 вариант расстановки, который можно четырежды повернуть на $\frac{\pi}{2}$, итого 4.
Для остальных нужно думать.

[Mihr]

arseniiv,
вот-вот. Задача сводится к расстановке ладей на непрямоугольной доске. Причём доска является таковой ещё до начала выбрасывания каких-то полей.
Красивого и изящного решения у меня не получилось (впрочем, и не ожидалось). Однако, скажем так, приемлемое решение получилось. Хотелось бы сравнить ответ, по возможности, с чужим ответом.
Booker48,
да, думать надо, конечно. Задача не из тех, что решается "с наскока". И, полагаю, не из тех, что можно решить в уме.

-- 17.10.2019, 09:21 --

arseniiv в сообщении #1421190 писал(а):

Это можно как-то удобно учесть?

Не знаю, сочтёте ли Вы это удобным... Я для решения этой задачи ввёл "ладейные числа" (не знаю, существуют ли такие на самом деле, скорее всего, существуют и, вероятно, называются как-нибудь иначе, я искать не стал). Под "ладейным числом" $L(n,k)$ в рамках этой задачи я понимаю количество способов расстановки произвольного числа не угрожающих друг другу ладей на прямоугольной доске заданных размеров $n \times k$, где $n \geqslant k$. Построил для таких чисел рекуррентное соотношение, на основании которого построил таблицу ладейных чисел. Далее с помощью довольно простых рассуждений свёл задачу о расстановке ладей на непрямоугольной доске к ряду задач о расстановке ладей на прямоугольных досках тех или иных размеров (опять некое подобие рекурсии). И таким образом добрался до ответа. Который и хотелось бы сравнить с чужим ответом.

[arseniiv]

Mihr в сообщении #1421208 писал(а):

Причём доска является таковой ещё до начала выбрасывания каких-то полей.

Если бы она оставалась «ромбической» как в начале, это было бы всё же неплохо, но нет.

Mihr в сообщении #1421208 писал(а):

Далее с помощью довольно простых рассуждений свёл задачу о расстановке ладей на непрямоугольной доске к ряду задач о расстановке ладей на прямоугольных досках тех или иных размеров

Вот это видится как самая неудобная и длинная часть, сколько это у вас заняло?

[Nemiroff]

https://arxiv.org/pdf/1609.00853.pdf
Формула (стр 9) весьма непохожа на элементарную.