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