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

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


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

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

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



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

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


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

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