KM11. 44 дерева по чижу на каждом

Задача
Задача из журнала «Квант» №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:

4 thoughts on “KM11. 44 дерева по чижу на каждом

  1. — «А если чижей и деревьев n ?» — здесь «n» это уже формула и кодировать ее нужно в latex.
    — Пожалуйста, не используйте символов кириллицы в постоянных ссылках.
    — Не забывайте указывать рубрику. Сейчас я делаю это за Вас, но в дальнейшем, пожалуйста, делайте это сами.
    — Ключевые слова не очень удачны. Постарайтесь «ухватить» суть задачи и выбрать те слова, которые существенны для этого текста.
    — «Значит, условие задачи доказано» — как это условие доказано?
    — «чижи не смогут при своем одновременном движении по и против часовой стрелки» — конечно не смогут! Одновременное движение в противоположных направлениях разрывает чижа пополам. Уж так чижи устроены.
    — Какая-то четная сумма выплывает… Сумма чего? Чижей и деревьев?

    — Вам нужно абсолютно точно воспроизвести решение задачи, приведенное в журнале. Пока писать своими словами у Вас не очень здорово получается. Давайте сначала поучимся на хорошем примере, а в следующий раз будем пытаться подражать этому образцу.

    • Спасибо за комментарий, буду исправлять.

    • Хорошо. Засчитал.
      Только на досуге доведите до конца — в журнале была еще сноска про необходимость и достаточность и обсуждение общего случая.

Добавить комментарий