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

Проект МЦНМО
при участии
школы 57
Задача 116267
Темы:    [ Примеры и контрпримеры. Конструкции ]
[ Соображения непрерывности ]
Сложность: 4
Классы: 8,9
В корзину
Прислать комментарий

Условие

Дракон заточил в темницу рыцаря и выдал ему 100 разных монет, половина из которых волшебные (какие именно – знает только дракон). Каждый день рыцарь раскладывает все монеты на две кучки (не обязательно равные). Если в кучках окажется поровну волшебных монет или поровну обычных, дракон отпустит рыцаря. Сможет ли рыцарь гарантированно освободиться не позже, чем
  а) на 50-й день?
  б) на 25-й день?


Решение

б) Сначала разложим монеты на две кучки: в первой – 49 монет, в второй – 51. Затем каждый день будем перекладывать по монете из первой кучки во вторую. На 25-й день в первой кучке будет 25 монет, во второй – 75. Стало быть, на 25-й день в первой кучке будет не больше 25 фальшивых и не больше 25 настоящих монет. Если такая же ситуация была и в первый день, то либо фальшивых, либо настоящих монет в первой кучке было ровно 25 штук (иначе всего монет там было бы не больше 48), и рыцарь освободился сразу. Иначе в первый день в первой кучке было больше 25 фальшивых или больше 25 настоящих монет. Заметим, что число как фальшивых, так и настоящих монет в первой кучке каждый день может измениться не больше, чем на 1, по сравнению с предыдущим днем. Поэтому в какой-то из дней между первым и 25-м число фальшивых или настоящих монет в первой кучке будет равно 25, что и требуется.


Ответ

Сможет.

Замечания

баллы: 2 + 3

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

олимпиада
Название Турнир городов
Турнир
Дата 2010/2011
Номер 32
вариант
Вариант весенний тур, базовый вариант, 8-9 класс
Задача
Номер 5

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

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