Имеется 100 серебряных монет, упорядоченных по весу, и 101 золотая монета, они также упорядочены по весу. Известно, что все монеты по весу различны. В нашем распоряжении – двухчашечные весы, позволяющие про каждые две монеты установить, какая тяжелее. Как за наименьшее число взвешиваний найти монету, занимающую среди всех монет 101-е место?
Задача была предложена в основном туре весеннего тура Турнира городов 1991/92 учебного года для 10-11 классов. Автор задачи - А.Анджанс.
Докажем, что если из 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-й из исходных.
Меньшим числом взвешиваний обойтись нельзя. Перед началом взвешиваний все монеты были претендентами на 101-е место. Взвешивание делит множество монет, которые были кандидатами на 101-е место, на два множества: те, которые ещё могут быть 101-й монетой, и оставшиеся. Результат взвешивания не известен. Поэтому может случиться так, что после первого взвешивания останется не менее 101 претендента; после второго - не менее 51; после третьего - не менее 26; после четвёртого - не менее 13; после пятого - не менее 7; после шестого - не менее 4; после седьмого - не менее 2.