ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 66518
Тема:    [ Теория алгоритмов (прочее) ]
Сложность: 4
Классы:
В корзину
Прислать комментарий

Условие

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

Решение

Ясно, что достаточно научиться переворачивать каждую из монет (сохраняя положение остальных).

Покажем сначала, как перевернуть пару монет, между которыми лежит ровно 6 монет. Если мысленно объединить эту пару с монетами между ними, получится группа из 8 монет подряд. Перевернём в этой группе 7 левых монет, затем 7 правых. Тогда крайние монеты перевернутся по разу, а промежуточные дважды (т.е. вернутся в исходное положение).

Пусть теперь мы хотим перевернуть какую-то одну монету. Будем считать, что она лежит в левой половине (для правой половины рассуждения аналогичны). Посмотрим на семёрку монет, первая из которых – выбранная нами, следующая лежит через 6 монет, следующая ещё через 6 и т.д.

Эта семёрка состоит из выбранной нами монеты и трёх пар, в которых монеты лежат с промежутками в 6. Поэтому мы можем перевернуть каждую из этих пар (как описано выше), а потом всю семёрку. В итоге положение сменит только выбранная монета.

Источники и прецеденты использования

олимпиада
Название Математический праздник
год
Год 2019
класс
Класс 7
задача
Номер 6

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .