The chess board

[отрава]

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.

[maciek]

I know the answer is m+n but I don't know how prove that

[bot]

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 - это ладья или, к примеру, лошадь? Автопереводчик нёс какую-то ахинею про грача.

[Профессор Снэйп]

bot писал(а):

Вчера вечером вспомнил про задачу и залез в бумажный словарь, а до того сомневался rock - это ладья или, к примеру, лошадь?

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

[bot]

Профессор Снэйп в сообщении #144203 писал(а):

Лошади в конюшне бывают, офицеры в казарме.

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

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

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

[Профессор Снэйп]

bot писал(а):

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

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

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

[Brukvalub]

Профессор Снэйп в сообщении #144714 писал(а):

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

Офицеры живут в офицерском общежитии или на съемных квартирах, или у себя дома.

Профессор Снэйп в сообщении #144714 писал(а):

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

Туры живут высоко в горах или в вольере зоопарка.

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

[вздымщик Цыпа]

Brukvalub в сообщении #144715 писал(а):

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

A как ходят батоны? И где они стоят в начале партии?

[TOTAL]

bot писал(а):

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

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

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

[maxal]

maciek писал(а):

I know the answer is m+n but I don't know how prove that

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

[Really]

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$ и не зависит.

[bot]

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$