Задача
а) На 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 перелётов попасть на то дерево, где сидит неподвижный чиж.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь