Увидеть граф (переформулировки)

Пронумеруем строки сверху вниз, а столбцы слева направо числами Построим ориентированный граф, вершинами которого будут клетки доски. Будем проводить ребро из клетки в клетку если жук переполз из клетки в клетку По условию из каждой вершины построенного графа выходит ровно ребро, и в каждую вершину графа входит ровно ребро. Значит, граф разбивается на циклы (некоторые циклы могут быть длины Рассмотрим один из таких циклов. Заметим, что он поровну раз переходит из строчки в строчку и обратно. Значит, и всего ребер из строки в строку и обратно будет поровну. В частности, количество жуков, сдвинувшихся влево, равно количеству жуков, сдвинувшихся вправо. Аналогичные рассуждения можно провести и со столбцами. Обозначим количество жуков, сдвинувшихся влево через количество жуков, сдвинувшихся вправо — через Понятно, что Заметим, что расстояние между жуками, сдвинувшимися в одном направлении, не изменилось. Тогда имеем хотя бы

пар жуков, расстояние между которыми не изменилось.