Задание по олимпиадной математике: замок 7×9 и путь по комнатам
Замок имеет вид прямоугольника размером 7×9 клеток. Каждая клетка, кроме центральной – комната замка, а в центральной клетке находится бассейн. В каждой стене (стороне клетки), разделяющей две соседние комнаты, проделана дверь. Можно ли, не выходя из замка и не заходя в бассейн, обойти все комнаты, побывав в каждой ровно по одному разу?
Показать ответ
Нельзя.
Разобрать решение
Окрасим клетки квадрата 7×9 в шахматном порядке, так что угловые клетки чёрные. При этом чёрных клеток будет на одну больше, чем белых. Легко проверить, что центральная клетка будет белой. Припишем комнатам замка чёрный и белый цвета в соответствии с этой шахматной раскраской. Тогда чёрных комнат будет на две больше, чем белых (чёрных – 32, белых – 30). При обходе комнат замка черные и белые комнаты чередуются, поскольку из чёрной комнаты можно войти только в белую, а из белой – только в черную. Поэтому обойти все комнаты нельзя.
Обсуждение
0Комментариев пока нет.