Олимпиадная задача о 100 серебряных и 101 золотой монете на весах: задача по олимпиадной математике для 7–9 классов

  Докажем, что если из 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-й по весу] (тогда эта вершина является концевой). Разветвлений на каждом пути не больше семи, следовательно, концевых вершин не больше  2⁷ = 128.  Но априори каждая из данных монет может оказаться на 101-м месте, то есть концевых вершин должно быть не меньше 201. Противоречие.

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