Задача М11‍‍

Решаем задачу сразу для $n$‍‍ чижей и $n$‍‍ деревьев. Занумеруем деревья по порядку (скажем, по часовой стрелке) числами от 1 до $n$‍‍ (рис. 1). Обозначим количество чижей на $k$‍‍-м дереве в какой-нибудь момент времени через $a_k$‍‍ (на первом дереве — $a_1$‍,‍ на втором — $a_2$‍‍ и т. д.). Рассмотрим выражение $$ S=1\cdot a_1+2\cdot a_2+\ldots+k\cdot a_k+\ldots+n\cdot a_n. $$ Покажем, что когда два чижа перелетают на соседние деревья в противоположных направлениях, то $S$‍‍ либо не меняется, либо меняется на $n$‍.‍

Действительно, пусть какой-то один чиж перелетает с $k$‍‍-го дерева на следующее по часовой стрелке. Тогда в сумме $S$‍‍ меняются два слагаемых. Если $k\lt n$‍,‍ то меняются $k$‍‍-e и $(k+1)$‍‍-е слагаемые, и их сумма становится равной $$ k(a_k-1)+(k+1)(a_{k+1}+1)=ka_k+(k+1)a_{k+1}+1, $$ т. е. увеличивается на 1. Если $k=n$‍,‍ то меняются $n$‍‍-e и первое слагаемые, а их сумма $$ n(a_n-1)+1(a_1+1)=na_n+1\cdot a_1-(n-1) $$ уменьшается на $n-1$‍.‍ Наоборот, если чиж перелетает на соседнее дерево против часовой стрелки, то сумма или уменьшается на 1, или увеличивается на $n-1$‍.‍ Поэтому, когда два чижа одновременно перелетают на соседние деревья (один по часовой стрелке, другой — против), то сумма $S$‍‍ или не меняется вовсе, или меняется нa $n$‍.‍

В начальный момент времени на каждом дереве сидело по одному чижу, $$ S=1\cdot1+2\cdot1+\ldots+n\cdot1=1+2+\ldots+n=\dfrac{n(n+1)}2. $$ Таким образом, после любого числа перелётов сумма будет равна $\dfrac{n(n+1)}2+np$‍,‍ где $p$‍‍ — некоторое целое число. Если бы все чижи собрались на каком-то одном $q$‍‍-м дереве, то $S$‍‍ было бы равно $nq$‍,‍ т. е. выполнялось бы равенство $\dfrac{n(n+1)}2+np=nq$‍,‍ откуда $n+1+2p=2q$‍;‍ $n=2(q-p)-1$‍.‍

Таким образом, если $n$‍‍ чётно, например, $n=44$‍,‍ то чижи не смогут собраться на одном дереве. Покажем, что при нечётных $n$‍‍ это может случиться‍.

Рассмотрим исходную ситуацию, когда на каждом дереве сидело по одному чижу. «Прикажем» одному чижу сидеть на месте и назовём его «неподвижным». Разобьём оставшихся чижей на пары сидящих на одинаковом расстоянии в $r$‍‍ перелётов от неподвижного в ту и другую сторону ($r=1$‍,‍ 2, $\ldots$‍,‍ $\dfrac{n(n-1)}2$‍).‍ Ясно, что каждая такая пара может за $r$‍‍ перелётов попасть на то дерево, где сидит неподвижный чиж.

Аналогичное решение прислали Д. Григорьев из г. Ленинграда, В. Лузгин из г. Георгиевска Ставропольского края и другие читатели.

Приведённое решение типично для задач, в которых требуется выяснить, можно ли в результате ряда каких-то преобразований получить определённый результат. В данном случае преобразование — это перелёт двух чижей в противоположных направлениях, и мы хотим выяснить, могут ли в результате все чижи собраться на одном дереве. Чтобы доказать, что можно, достаточно привести пример, как это сделать. Доказать, что ни при каких преобразованиях нельзя получить требуемый результат, часто бывает удобно так: найти какую-то величину, которая сохраняется при всех рассматриваемых преобразованиях и для которой начальное значение отличается от требуемого в конечном состоянии (такая величина называется инвариантом данных преобразований). В нашей задаче такой величиной является остаток от деления суммы $S$‍‍ на $n$‍.‍

Тем, кто решил эту задачу, будет интересно разобраться в следующем более общем вопросе. Пусть даны два разных расположения $a$‍‍ чижей на $n$‍‍ деревьях. Назовём их эквивалентными, если из одного можно получить другое (при перелётах чижей, как указано в условии задачи). Как узнать, будут ли эти расположения эквивалентны? Ещё один вопрос. Ясно, что множество всех возможных расположений $a$‍‍ чижей на $n$‍‍ деревьях распадается на несколько классов эквивалентности. Сколько будет таких классов?

Дополнение к решению задачи M11 (см. «Квант» № 11).

Итак, выясним, сколько существует неэквивалентных расположений $a$‍‍ чижей на $n$‍‍ деревьях (напомним, что два расположения считаются эквивалентными, если из одного может получиться другое при перелётах чижей, разрешённых условием задачи: один чиж — на соседнее дерево по часовой стрелке, другой — против). Уточним постановку задачи. Деревья мы считаем отличимыми друг от друга — занумеруем их по кругу числами 0, 1, 2, $\ldots$‍,‍ $n-1$‍,‍ а чижей — неотличимыми друг от друга, т. е. нас интересует только набор чисел $a_0$‍,‍ $a_1$‍,‍ $a_2$‍,‍ $\ldots$‍,‍ $a_n$‍,‍ где $a_k$‍‍ — число чижей на $k$‍‍-м дереве, но не интересует, какой именно чиж где находится‍. Мы уже пользовались тем, что величина остатка от деления нал суммы $a_1+2a_2+3a_3+\ldots+(n-1)a_{n-1}$‍‍ (обозначим этот остаток $r$‍)‍ не меняется при перелётах чижей. Кроме того, ясно, что не меняется общее число чижей: $a_0+a_1+\ldots+a_{n-1}=a$‍.‍

Таким образом, если два расположения чижей эквивалентны, то у них одинаковы величины $a$‍‍ и $r$‍.‍ Докажем, что, обратно, если у двух расположений $a$‍‍ чижей величина $r$‍‍ одна и та же, то они эквивалентны. А именно мы покажем, что каждое расположение с данным $r$‍‍ можно перелётами чижей свести к такому: все чижи собрались на дереве номер 0, кроме одного, который сидит на дереве номер $r$‍‍.

Это сделать нетрудно. Назовём одного чижа «летуном» и будем каждого из остальных чижей переводить на нулевое дерево, заставляя при этом в паре с ним двигаться в нужную сторону «летуна». Ясно, что всех можно собрать на дереве 0, кроме «летуна», окончательное положение которого определяется числом $r$‍.‍

Итак, множество всех возможных расположений $a$‍‍ чижей на $n$‍‍ деревьях состоит из $n$‍‍ классов эквивалентности ($r=0$‍,‍ 1, $\ldots$‍,‍ $n-1$‍).‍