2014 dxdy logo

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

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




 
 The chess board
Сообщение09.09.2008, 20:09 
Rooks have been placed on some fields of a chess board of size m x n and (m,n \geq 2). Each of the rooks is under attack by at most two other rooks. Find the maximum amount of rooks, for which such a situation is possible.

 
 
 
 
Сообщение11.09.2008, 16:33 
I know the answer is m+n but I don't know how prove that :?

 
 
 
 
Сообщение13.09.2008, 07:55 
Аватара пользователя
For board $m\times n, \ m,n \geqslant 0$ let $R(m,n)$ be the number of rocks in the question.
Evidently we have
$R(m,n)=R(n,m),\  R(0,n)=0,\  R(1,1)=1,\  R(1,2)=2,\  R(2,2)=4$

For $m\times n$ board at least $2\min (m,n)$ rocks can be plased:
xxooo...oo...
oxxoo...oo...
ooxxo...oo...
.................
ooooo...xx...
xoooo...ox...

By considerating any line (column) which may contain 3 rocks we get obvious recursion:

$R(m,n)=\max (2\min (m,n), 3+R(\min (m,n)-1, \max (m,n)-3) )$

Добавлено спустя 5 минут 56 секунд:

In particular $R(n,n)=2n$ for $n>1$

Судя по нику аскера можно было и по-русски отвечать.
Вчера вечером вспомнил про задачу и залез в бумажный словарь, а до того сомневался rock - это ладья или, к примеру, лошадь? Автопереводчик нёс какую-то ахинею про грача. :D

 
 
 
 
Сообщение13.09.2008, 08:30 
Аватара пользователя
bot писал(а):
Вчера вечером вспомнил про задачу и залез в бумажный словарь, а до того сомневался rock - это ладья или, к примеру, лошадь?


Лошади в конюшне бывают, офицеры в казарме. А на шахматной доске --- кони и слоны!

 
 
 
 
Сообщение16.09.2008, 05:13 
Аватара пользователя
Профессор Снэйп в сообщении #144203 писал(а):
Лошади в конюшне бывают, офицеры в казарме.

Ну одного офицера в казарме ещё можно представить - зашёл проверить солдатское житие-битие, а чтоб во множественном числе ...

А из рекуррентной формулы легко вытекает, что для $ 2\leqslant m\leqslant n$

$$R(m,n)=\Big[\frac{9m+n-|n-3m|}{4}\Big]$$

 
 
 
 
Сообщение16.09.2008, 06:04 
Аватара пользователя
bot писал(а):
Ну одного офицера в казарме ещё можно представить - зашёл проверить солдатское житие-битие, а чтоб во множественном числе ...


А где они тогда живут? Я думал, что казарма --- это не только для солдат, но и для офицеров тоже. Типа специальная такая офицерская казарма.

Ещё интересно, где туры живут.

 
 
 
 
Сообщение16.09.2008, 06:09 
Аватара пользователя
Профессор Снэйп в сообщении #144714 писал(а):
А где они тогда живут? Я думал, что казарма --- это не только для солдат, но и для офицеров тоже. Типа специальная такая офицерская казарма.
Офицеры живут в офицерском общежитии или на съемных квартирах, или у себя дома.
Профессор Снэйп в сообщении #144714 писал(а):
Ещё интересно, где туры живут
Туры живут высоко в горах или в вольере зоопарка.

На всякий случай также сообщу, что батоны хлеба не растут на хлебных деревьях, а их выпекают из муки в хлебопекарнях.

 
 
 
 
Сообщение16.09.2008, 06:47 
Brukvalub в сообщении #144715 писал(а):
На всякий случай также сообщу, что батоны хлеба не растут на хлебных деревьях, а их выпекают из муки в хлебопекарнях.
A как ходят батоны? И где они стоят в начале партии?

 
 
 
 
Сообщение16.09.2008, 06:48 
Аватара пользователя
bot писал(а):
А из рекуррентной формулы легко вытекает, что для $ 2\leqslant m\leqslant n$

$$R(m,n)=\Big[\frac{9m+n-|n-3m|}{4}\Big]$$

При больших $n$ зависит только от $m$. То есть неверная формула.

 
 
 
 
Сообщение16.09.2008, 08:09 
Аватара пользователя
maciek писал(а):
I know the answer is m+n but I don't know how prove that :?

Ну да, $m+n$ (при $n,m\geq 2$) дает расстановка "уголком" (ладьи стоят на всех клетках верхней горизонтали и левой вертикали) + одна ладья в противоположном углу. Легко видеть, что больше поставить нельзя.

 
 
 
 
Сообщение16.09.2008, 08:15 
TOTAL в сообщении #144717 писал(а):
bot писал(а):
А из рекуррентной формулы легко вытекает, что для $ 2\leqslant m\leqslant n$

$$R(m,n)=\Big[\frac{9m+n-|n-3m|}{4}\Big]$$

При больших $n$ зависит только от $m$. То есть неверная формула.


Так, а при $n\geqslant 3m$ указанное выражение от $n$ и не зависит.

 
 
 
 
Сообщение16.09.2008, 08:37 
Аватара пользователя
maxal писал(а):
maciek писал(а):
I know the answer is m+n but I don't know how prove that :?

Ну да, $m+n$ (при $n,m\geq 2$) дает расстановка "уголком" (ладьи стоят на всех клетках верхней горизонтали и левой вертикали) + одна ладья в противоположном углу. Легко видеть, что больше поставить нельзя.

Я считал, что ладья может бить сквозь ладью, а это другая задача.

Добавлено спустя 2 минуты 7 секунд:

Really в сообщении #144725 писал(а):
Так, а при указанное выражение от и не зависит.

Ну дык я просто объединил два случая. При $n\ge 3m$ очевидно $R(m,n)=3m$

 
 
 [ Сообщений: 12 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group