Не более одного другого ферзя

[Ktina]

Какое наибольшее количество ферзей можно поставить на (изначально пустую) шахматную доску так, чтобы каждый ферзь бил не более одного другого ферзя?

[Ktina]

Пример из 10 ферзей строится легко, но вот можно ли больше 10, в этом вся загадка.

[waxtep]

Десять можно, у меня получилось так: два бьют друг друга через всю главную диагональ $h1-a8$, и еще два неравных косых квадратика $d2-g4-e7-b5$ и $f2-g6-c7-b3$. А больше как-то слабО...

[Gagarin1968]

Ktina в сообщении #1338472 писал(а):

Пример из 10 ферзей строится легко, но вот можно ли больше 10, в этом вся загадка.

Ktina
Похоже, что больше нельзя.
Из условия задачи очевидно, что на одной горизонтали или вертикали не могут располагаться более $2 $ ферзей.
Введём обозначения:
$p_0, q_0$ - количество соответственно горизонталей и вертикалей, свободных от ферзей.
$p_1, q_1$ - количество соответственно горизонталей и вертикалей с одним ферзём.
$p_2, q_2$ - количество соответственно горизонталей и вертикалей с двумя ферзями.
Поскольку $p_0+p_1+p_2=8$, то $p_1+p_2\leqslant 8$.
Аналогично $q_0+q_1+q_2=8\Longrightarrow q_1+q_2\leqslant 8$.
Далее, в $p_2$ горизонталях находятся $2p_2$ ферзей, и каждый из этих ферзей уже бьёт одного ферзя. А из этого следует, что по меньшей мере в $2p_2$ вертикалях находится только по одному ферзю. Таким образом, $2p_2\leqslant q_1$, и аналогично $2q_2\leqslant p_1$.
Искомое количество ферзей $x=p_1+2p_2=q_1+2q_2$. А отсюда легко находим верхнюю границу для $x$:

$x=\displaystyle \frac {p_1+2p_2+q_1+2q_2}{2}\leqslant \displaystyle \frac {p_1+\displaystyle \frac {4}{3}p_2+\displaystyle \frac {1}{3}q_1+q_1+ \displaystyle \frac {4}{3}q_2+\displaystyle \frac {1}{3}p_1}{2}=\displaystyle \frac {2(p_1+p_2+q_1+q_2)}{3}=$ $\displaystyle \frac {32}{3}$

Т.е. $x<11$ - верхняя граница для количества ферзей.
Ну, как-то так. Вроде нигде не ошибся.

[Ktina]

Gagarin1968
Большое спасибо!

[Gagarin1968]

Ktina
Да, и, между прочим, эту задачу можно обобщить для доски произвольного размера $k\times k$. Если в полученной оценке заменить $8$ на $k$, то получим верхнюю оценку количества ферзей $x=\displaystyle \frac {4}{3}k$.