|
|
 |
Условие
Имеется 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.
