Задача
Задача из журнала «Квант» №11-1970г.

На 44 деревьях, расположенных по окружности, сидели 44 веселых чижа (на каждом дереве по чижу). Время от времени два чижа одновременно перелетают на соседние деревья в противоположных направлениях (один – по часовой стрелке, второй – против). Докажите, что чижи никогда не соберутся на одном дереве. А если чижей и деревьев [latex]n[/latex]?

Входные данные

[latex]n[/latex] – количество деревьев.

Выходные данные

«Yes» или «No».

Тесты

Входные данные	Выходные данные
10	No
15	Yes

Код программы

Код программы на С++

Код программы на Java

Решение

Решаем задачу сразу для [latex]n[/latex] чижей и [latex]n[/latex] деревьев. Обозначим количество чижей на [latex]k[/latex]-м дереве в какой-нибудь момент времени через [latex]a_{k}[/latex] (на первом дереве – [latex]a_{1} [/latex], на втором – [latex]a_{2}[/latex] и т.д.). Рассмотрим выражение [latex]S=1a_{1}+2a_{2}+\ldots+ka_{k}+\ldots+na_{n}[/latex]. Когда два чижа перелетают на соседние деревья в противоположных направлениях, то [latex]S[/latex] либо не меняется, либо меняется на [latex]n[/latex].
Действительно, пусть какой-то один чиж перелетает с [latex]k[/latex]-го дерева на следующее по часовой стрелке. Тогда в сумме [latex]S[/latex] меняются два слагаемых. Если [latex]k<n[/latex], то меняются [latex]k-1[/latex] и [latex]k+1[/latex] — е слагаемые, и их сумма становится равной [latex]k(a_{k}-1)+(k+1)(a_{k+1}+1)=ka_{k}+(k+1)a_{k+1}+1[/latex], то есть увеличивается нa 1. Если [latex]k=n[/latex], то меняется [latex]n[/latex] -е и первое слагаемые, а их сумма [latex]n(a_{n}-1)+1(a_{1}+1)=na_{n}+a_{1}-(n-1)[/latex] уменьшается на [latex]n-1[/latex]. Наоборот, если чиж перелетает на соседнее дерево против часовой стрелки, то сумма или уменьшается на 1, или увеличивается на [latex]n-1[/latex]. Поэтому, когда два чижа одновременно перелетают на соседние деревья (один по часовой стрелки, другой — против), то сумма [latex]S[/latex] или не меняется вовсе, или меняется на [latex]n[/latex]. В начальный момент времени на каждом дереве сидело по одному чижу, [latex]S=1\cdot1+2\cdot1+\ldots+n\cdot1=1+2+\ldots+n=\frac{n\left(n+1\right)}{2}[/latex].
Таким образом, после любого числа перелетов сумма будет равна [latex]\frac{n(n + 1)}{2} + np[/latex], где [latex]p[/latex] – некоторое целое число. Если бы все чижи собрались на каком-то одном [latex]q[/latex]-дереве, то [latex]S[/latex] было бы равно [latex]nq[/latex], то есть выполнялось бы равенство [latex]\frac{n(n + 1)}{2} + np = nq[/latex], откуда [latex]n + 1 + 2p = 2q[/latex], [latex]n=2(q-p)-1[/latex].
Таким образом, если [latex]n[/latex] четно, например, [latex]n[/latex] = 44, то чижи не смогут собраться на одном дереве. Покажем, что при нечетных [latex]n[/latex] это может случиться.
Рассмотрим исходную ситуацию, когда на каждом дереве сидело по одному чижу. «Прикажем» одному чижу сидеть на месте и назовем его «неподвижным». Разобьем оставшихся чижей на пары сидящих на одинаковом расстоянии в [latex]r[/latex] перелетов от неподвижного в ту и другую сторону ([latex]r=1,2,\ldots,\frac{n-1}{2}[/latex]).
Ясно, что каждая такая пара может за [latex]r[/latex] перелетов попасть на то дерево, гдe сидит неподвижный чиж.
Приведенное решение типично для задач, в которых требуется выяснить, можно ли в результате ряда каких-то преобразований получить определенный результат. В данном случае преобразование – это перелет двух чижей в противоположных направлениях, и мы хотим выяснить, могут ли в результате все чижи собраться на одном дереве. Чтобы доказать, что можно, достаточно привести пример, как это делать. Доказать, что ни при каких преобразованиях нельзя получить требуемый результат, часто бывает удобно так: найти какую-то величину, которая сохраняется при всех рассматриваемых преобразованиях и для которой начальное значение отличается от требуемого в конечном состоянии (такая величина называется инвариантом данных преобразований). В нашей задаче такой величиной является остаток от деления суммы [latex]S[/latex] на [latex]n[/latex].

Ссылка: Условие задачи
Ccылка: Решение задачи на сайте Ideone.com (C++)
Ccылка: Решение задачи на сайте Ideone.com (Java)

Related Images: