Задача 1.
9 гномов поселились в 9 комнатах, расположенных в виде квадрата 3 × 3. Как только они поселились, каждый пожал руки своим соседям (соседи по стороне). На второй день они поселились по-другому, и каждый пожал руки своим новым соседям. На третий день они снова переселились, и снова, каждый пожал руки каждому своему соседу. Докажите, что после трёх дней найдутся два гномика, которые не жали руки друг другу.
Ответ на Задачу 1.
Пускай не найдутся. Тогда каждый сделал 8 рукопожатий. На каждом переселении у гномика может быть либо 2, либо 3, либо 4 соседа. Тогда есть только два варианта разложения: 4 + 2 + 2 и 3 + 3 + 2 с точностью до перестановки. Значит, все три раза центральная клетка была занята разными гномиками. Покрасим теперь шахматной раскраской так, чтобы центральная была чёрной. Но две изначально чёрные клетки могут двигаться только по чёрным клеткам. Тогда заметим, что изначально чёрная изначально не может соседствовать с другой изначально чёрной. Значит, они никогда не будут соседями, хотя должны. Противоречие.
