Республиканская олимпиада по математике, 2011 год, 10 класс

На некоторых клетках прямоугольной таблицы $m\times n$ $(m,n > 1)$ стоит по одной шашке. Малыш разрезал по линиям сетки эту таблицу так, что она распалась на две одинаковые части, при этом количество шашек на каждой части оказались одинаковыми. Карлсон поменял расстановку шашек на доске (причем на каждой части клетке по прежнему стоит не более одной шашки). Докажите, что Малыш может снова разрезать доску на две одинаковые части, содержащие равное количество шашек. ( Н. Седракян )

Комментарий/решение

Из условия выводим что количество клеток и шашек четно. Боо $n$ четное. Тогда заметим что центр доски лежит на узле длиной $m$ разделяющий доску на два равных прямоугольника $m \times \frac{n}{2}$ сверху и снизу, и далее у нас получается что у каждой клетки есть ровно одна симметричная ей клетка относительно центра.

Будем красить каждую клетку в красный или синий, причем симметричные друг другу клетки разных цветов, данная операция идентична с разрезом доски на одинаковые части в случае если клетки каждого цвета связны. Заметим что как бы мы не красили пары клеток с равным количеством шашек то это не вляет на разницу в количестве шашек, можем считать что у каждой пары либа одна шашка либо нет шашек.

Посчитаем количество $t$ пар клеток где в одной есть шашка а в другой нет, заметим что $t$ четное. БОО в прямоугольнике $m\times \frac{n}{2}$ сверху больше шашек (больше чем $t/2$) из этих $t$ пар чем снизу, случай где у них количества равны сразу решает задачу.

Проведем следующую операцию:

Если в левом столбце прямоугольника сверху не больше $t/2$ шашки, начиная с самого левого столбца будем красить в красный клетки каждого столбца начиная сверху пока не покрасим ровно $t/2$ шашки плюс пустые клетки до следующей шашки, остальные клетки с синий в частности остальные шашки. У нас левый столбец полностью красный и в силу симметрии мы раскрасили доску сохраняя связность.

Если в левом столбце больше чем $t/2$ шашки то у правой явно меньше чем $t/2$ так как у нас в общем $t$ шашки, тогда красим начиная с правого столбца, идентично раскраске в предыдущем параграфе что также удовлетворяет задаче.