Олимпиадная задача для 8 класса: наименьшее число цепочек

[Null]

Задача с Уральского турнира юных математиков. Ни одна команда эту задачу не решила.

Пусть есть клетчатый прямоугольник m x n. На какое наименьшее число цепочек ее можно разрезать. Разрешены цепочки из клеточек, идущие слева направо и сверху вниз, или слева направо и снизу вверх, соседние клеточки в цепочках имеют общую сторону.

Угадать ответ легко.

от модератора AD:

Уточнил заголовок темы.

[arqady]

Null в сообщении #356922 писал(а):

Разрешены цепочки из клеточек, идущие слева направо и сверху вниз, или слева направо и снизу вверх,

То бишь по диагонали. Но тогда это противоречит

Null в сообщении #356922 писал(а):

соседние клеточки в цепочках имеют общую сторону.

тогда

Null в сообщении #356922 писал(а):

Угадать ответ легко.

Нисколько.

[ewert]

ну, меньше чем на одну-то уж точно не разрежешь

[Null]

11111
22441
23331
23551
33561
Вот пример разбиения. Странно думал понятно написал. Как это лучше записать?

[EtCetera]

Null
Все равно непонятно, только уже немного другое. Что мешает пустить цепочку "змейкой" ("синусоидой") и достичь тем самым теоретически наименьшего возможного ответа 1?

[Null]

эти цепочки должны идти либо вверх и влево, либо вниз и влево

[gris]

Каждая цепочка как бы образуется ходами ладьи, которая каждый раз по вертикали ходит только в одном направлении и по горизонтали тоже. А, ну уже сказали. Кстати, вправо-вниз и вправо-вверх тоже проходит (по симметрии).
Есть тривиальное решение из $\min(n;m)$ цепочек. А вот можно ли меньше - в этом и олимпиадность, наверное.

[Null]

gris в сообщении #357007 писал(а):

Каждая цепочка как бы образуется ходами ладьи, которая каждый раз по вертикали ходит только в одном направлении и по горизонтали тоже. А, ну уже сказали. Кстати, вправо-вниз и вправо-вверх тоже проходит (по симметрии).
Есть тривиальное решение из $\min(n;m)$ цепочек. А вот можно ли меньше - в этом и олимпиадность, наверное.

Во так правильно.