Подсчеты в клетчатых задачах

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

подходящих пар. То есть всего нужных нам пар не меньше, чем

Поймем, в каких случаях расстояние между жуками не изменяется. Пусть разность между абсциссами жуков равна а разность между ординатами равна Тогда после передвижений квадрат расстояния между жуками может быть равен (если жуки движутся в одном направлении), либо или (если жуки движутся в противоположных направлениях), что нам не походит, либо что нам также не подходит, также как и либо или наоборот. В последнем случае имеем откуда или наоборот.

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