Назад
Задача

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

б) А если чижей и деревьев n?

Решение

  а) Занумеруем деревья по порядку, начиная с некоторого дерева. Для каждого чижа рассмотрим номер дерева, на котором он сидит, и сложим эти 44 номера. Заметим, что в процессе перелетания чижей эта сумма либо не менятся, либо меняется на 44. Следовательно, остаток от деления данной суммы на 4 остается неизменным. Вначале сумма номеров деревьев равна  1 + 2 + ... + 44 = 22·45,  что даёт остаток 2 от деления на 4. Но если все чижи перелетят на одно дерево с номером n, то рассматриваемая сумма станет равной 44n, что кратно 4. Значит, это невозможно.   б) Занумеруем деревья по порядку (скажем, по часовой стрелке) числами от 1 до n и рассмотрим сумму, аналогичную рассмотренной в п. а).

  Когда два чижа перелетают на соседние деревья в противоположных направлениях, то S либо не меняется, либо меняется на n.

  В начальный момент  S = ½ n(n + 1).  Таким образом, после любого числа перелётов сумма будет равна  ½ n(n+1) + np,  где p – некоторое целое число. Если все чижи собираются на каком-то одном q-м дереве, то S становится равным nq. Равенство  ½ n(n + 1) + np = nq  приводится к виду

n = 2(q – p) – 1.  Таким образом, если n чётно, то чижи не смогут собраться на одном дереве.

  Покажем, что при нечётных n это возможно. "Прикажем" одному чижу сидеть на месте и назовем его неподвижным. Разобьём оставшихся чижей на пары сидящих на одинаковом расстоянии в r перелётов от неподвижного в ту и другую сторону  (r = 1, 2, ..., n–1/2).  Ясно, что каждая такая пара может за r перелётов попасть на то дерево, где сидит неподвижный чиж.

Ответ

Ответ задачи отсутствует

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Комментариев нет