|
|
 |
Условие
Али-Баба стоит с большим мешком монет в углу пустой прямоугольной пещеры размером m×n клеток, раскрашенных в шахматном порядке. Из любой клетки он может сделать шаг в любую из четырёх соседних клеток (вверх, вниз, вправо или влево). При этом он должен либо положить одну монету в этой клетке, либо забрать из неё одну монету, если, конечно, она не пуста. Может ли после прогулки Али-Бабы по пещере оказаться, что на чёрных клетках лежит ровно по одной монете, а на белых монет нет?
Решение
Прямоугольник m×n можно обойти "змейкой", проходя каждую клетку по одному разу (см. рисунок для прямоугольника 4×4).
"Усложним" задачу, запретив Али-Бабе класть монету в клетку, где монета уже есть (то есть при ходе в клетку, где уже есть монета, он будет обязан её забрать). Заметим, что если Али-Баба будет следовать этому правилу, то ни в какой клетке не может оказаться две монеты.
Итак, пойдём по пещере (вместе с Али-Бабой) "змейкой" с мешком монет
и будем стараться, чтобы в каждой клетке оказалось требуемое (правильное) количество монет. Сделав очередной ход, будем проверять, правильное ли количество монет на клетке, с которой мы только что ушли. Если правильное, то будем спокойно идти дальше. А если неправильное, то возможно только два варианта: 0 вместо 1 и 1 вместо 0. Сделаем шаг назад, изменим состояние "неправильной" клетки, а потом сделаем шаг вперёд.
Так, клетка за клеткой, мы добьёмся того, что на всех клетках, кроме, может быть, самой последней, – правильное количество монет. Если на последней клетке неправильное количество монет, то, пойдя назад, вперёд и назад,
мы добьёмся, что на всех клетках будет правильное количество монет.
Ответ
Может.
