Птицы перелетают в противоположные стороны

Условие

По кругу растут $44$ дерева, на каждом сидит одна птица. За ход выбирают двух птиц: одна перелетает на соседнее дерево по часовой стрелке, другая — на соседнее дерево против неё. На одном дереве может сидеть сколько угодно птиц. Могут ли когда-нибудь все птицы собраться на одном дереве?

О задаче · Продвинутый уровень · школьники и взрослые

Тема: Остатки и инварианты
Для кого: Продвинутый уровень · школьники и взрослые
Уровень библиотеки: Продвинутый · ориентир

Записать идею

Личный черновик для заметок и расчётов. Он никуда не отправляется и не проверяется.

Подсказка 1

Пронумеруйте деревья от $0$ до $43$ и сложите номера деревьев, на которых сидят птицы.

Подсказка 2

При переходе через границу нумерации сумма может измениться на $44$ Рассматривайте только остаток от деления на $44$

Разобрать решение по шагам

Замените движение числами

Номера деревьев расположены по кругу, поэтому после $43$ снова идёт $0$ Перелёт по часовой стрелке увеличивает номер на $1$ с точностью до кратного $44$ а противоположный уменьшает на $1$ В паре изменения взаимно уничтожаются по остатку.

Вычислите исходный остаток

Вначале сумма номеров равна

0+1+\cdots+43=\frac{44\cdot43}{2}=946.

Это число даёт остаток $22$ при делении на $44$ После любого количества ходов остаток суммы останется $22$

Сравните с конечной целью

Если все $44$ птицы сидят на дереве с номером $k$ сумма номеров равна $44k$ и делится на $44$ Её остаток равен $0$ а не $22$ Значит, общий сбор невозможен.

Сумма номеров сохраняется по модулю 44

010+1+…+43 = 946остаток 22 при делении на 44

02+1 и −1каждый совместный перелёт

0344 × kостаток 0 при общем сборе

Ответ

Нельзя

Главная идея

На круге удобнее сохранять не обычную сумму, а её остаток по числу позиций.

Как заметить эту идею в другой задаче

Два движения по кругу направлены противоположно. Нумерация скачет на границе круга, поэтому отслеживайте остаток суммы номеров, а не саму сумму.

Возможная ошибка

Утверждать, что обычная сумма номеров всегда постоянна: при перелёте через границу $43\leftrightarrow 0$ она меняется на кратное $44$

Источник и примечания

Источник и редакция

А. В. Спивак. «Тысяча и одна задача по математике. 5–7 классы», 2002. С. 78, № 491 (вторая задача с этим номером, о чижах). Условие пересказано, объяснение и дополнительное упражнение подготовлены для сайта.

Проверь себя

Изменится ли ответ для $45$ деревьев и $45$ птиц?

Ответ к дополнительной задаче

Да, собрать всех можно. Выберите целевое дерево $0$ Остальные разбиваются на $22$ пары на равных расстояниях $k=1,\ldots,22$ по обе стороны от него. Для каждой пары одновременно двигайте обеих птиц к нулю $k$ раз. Их направления противоположны. За

1+\cdots+22=253

совместных хода все окажутся у цели.

Продолжить тему: Остатки и последние цифры →

Тема, знания и приёмы

Остатки и последние цифры · Нужна школьная база

Деление с остатком
Нумерация мест по кругу

Приёмы решения: Инвариант или монотонная величина

Задать вопрос по задаче →

Условие

Замените движение числами

Вычислите исходный остаток

Сравните с конечной целью

Источник и редакция

Условие

Дополнительная задача