2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Не более одного другого ферзя
Сообщение12.09.2018, 19:35 
Аватара пользователя


01/12/11

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

 Профиль  
                  
 
 Re: Не более одного другого ферзя
Сообщение12.09.2018, 23:43 
Аватара пользователя


01/12/11

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

 Профиль  
                  
 
 Re: Не более одного другого ферзя
Сообщение13.09.2018, 01:02 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Не более одного другого ферзя
Сообщение15.09.2018, 00:09 
Аватара пользователя


01/11/14
2046
Principality of Galilee
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$ - верхняя граница для количества ферзей.
Ну, как-то так. Вроде нигде не ошибся.

 Профиль  
                  
 
 Re: Не более одного другого ферзя
Сообщение15.09.2018, 00:54 
Аватара пользователя


01/12/11

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

 Профиль  
                  
 
 Re: Не более одного другого ферзя
Сообщение15.09.2018, 01:48 
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

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



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

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

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