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

Проект МЦНМО
при участии
школы 57
Задача 98177
Темы:    [ Четность и нечетность ]
[ Инварианты ]
Сложность: 2+
Классы: 6,7,8
В корзину
Прислать комментарий

Условие

Автор: Гусаров М.

Есть три кучи камней. Разрешается к любой из них добавить столько камней, сколько есть в двух других кучах, или из любой кучи выбросить столько камней, сколько есть в двух других кучах. Например:  (12, 3, 5)  →  (12, 20, 5)  (или  (4, 3, 5)).  Можно ли, начав с куч 1993, 199 и 19, сделать одну из куч пустой?


Решение

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

Ответ

Нельзя.

Замечания

1. 4 балла.

1. Задача станет значительно интереснее, если в третьей куче изначально будет не 19, а 18 камней. Вот конспект её решения.
  Если начать выбрасывать камни, то придётся сначала несколько раз выбросить из первой кучи по 217 камней, пока не получится набор  (40, 199, 18);  затем мы придём к набору  (40, 25, 18),  из которого уже ничего не вычтешь. Не удастся поправить положение, добавляя в одну из куч камни (в тот или иной момент)? В самом деле, если после добавления, например, в первую кучу мы затем производим выбрасывание, то выбрасывать придётся непременно из той же первой кучи, то есть мы вернёмся к исходному положению. Точно так же, если сделать несколько прибавлений, а уж затем – выбрасывания, легко убедиться, что и здесь придётся "идти обратно по уже пройденному пути".

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

олимпиада
Название Турнир городов
Турнир
Дата 1992/1993
Номер 14
вариант
Вариант весенний тур, тренировочный вариант, 10-11 класс
Задача
Номер 4

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

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