Математикадан республикалық олимпиада, 2010-2011 оқу жылы, 10 сынып

Өлшемі $m\times n$ болатын тақтаның кейбір шаршыларына дойбы тастары бір-бірден қойылған. Балақай тақтаны тор сызықтарының бойымен қиған кезде, ол екі тең бөлікке бөлінді және екі бөліктегі дойбы тастарының саны өзара тең болды. Карлсон дойбы тастарын орындарынан жылжытып, олардың тақтадағы қойылымын өзгертті (бірақ бұрынғыдай әр шаршыда көп дегенде бір дойбы тасы тұр). Балақай тағы да тақтаны үстіндегі дойбы тастарының саны тең болатындай етіп, екі тең бөлікке бөле алатындығын дәлелде. ( Н. Седракян )

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

Из условия выводим что количество клеток и шашек четно. Боо $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$ шашки, тогда красим начиная с правого столбца, идентично раскраске в предыдущем параграфе что также удовлетворяет задаче.