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

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

Условие

Автор: Анджанс А.

Имеется 100 серебряных монет, упорядоченных по весу, и 101 золотая монета, они также упорядочены по весу. Известно, что все монеты по весу различны. В нашем распоряжении – двухчашечные весы, позволяющие про каждые две монеты установить, какая тяжелее. Как за наименьшее число взвешиваний найти монету, занимающую среди всех монет 101-е место?


Решение

  Докажем, что если из n серебряных и n золотых монет за k взвешиваний можно найти n-ю по весу монету, то за  k + 1  взвешивание можно найти 2n-ю по весу из 2n серебряных и 2n золотых.
  Действительно, пусть n-я серебряная весит больше n-й золотой. Тогда n первых серебряных занимают по весу места выше 2n-го, так как они тяжелее
n серебряных и  n + 1  золотых монет. С другой стороны, n последних золотых монет должны занимать места ниже 2n-го, так как они легче n золотых и
n серебряных монет. Значит, искомая монета – среди оставшихся n легких серебряных и n тяжелых золотых и занимает среди них n-е место; она находится за k оставшихся взвешиваний.

  Пример. За одно взвешивание можно найти более тяжелую монету из двух, следовательно за 8 взвешиваний можно найти 128-ю из 128 серебряных и 128 золотых.
  Добавим мысленно к нашим монетам 27 золотых (14 очень тяжелых и 13 очень легких) и 28 серебряных (14 тяжелых и 14 легких) и применим к ним описанный выше алгоритм. 128-я из этих 256 монет будет 101-й из исходных.

  Оценка. Предположим, что можно определить нужную монету за 7 взвешиваний. Рассмотрим блок-схему алгоритма, позволяющего это сделать. Эта блок-схема имеет вид дерева, в каждой вершине которого стоит либо проверка [какая из двух определенных монет легче?] (тогда из этой вершины идет разветвление в две следующие вершины); либо ответ [такая-то монета является 101-й по весу] (тогда эта вершина является концевой). Разветвлений на каждом пути не больше семи, следовательно, концевых вершин не больше  27 = 128.  Но априори каждая из данных монет может оказаться на 101-м месте, то есть концевых вершин должно быть не меньше 201. Противоречие.


Ответ

8 взвешиваний.

Замечания

1. 12 баллов

2. Несколько другое решение см. в решениях Задачника «Кванта», 1992, №12.

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

журнал
Название "Квант"
год
Год 1992
выпуск
Номер 6
Задача
Номер М1347
олимпиада
Название Турнир городов
Турнир
Дата 1991/1992
Номер 13
вариант
Вариант весенний тур, основной вариант, 10-11 класс
Задача
Номер 5

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

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