Показать скрытый текст
Расположим золотые монеты в ряд по убыванию масс, серебряные под ними в другой ряд — по возрастанию, и соединим соседние монеты отрезками, как показано на рисунке (в первой строчке монеты золотые, во второй — серебряные).
Каждый отрезок соединяет две монеты. Придадим ему направление от тяжелой монеты к легкой, так чтобы каждый отрезок превратился в стрелочку. Эти стрелочки обладают тем свойством, что если какая-то направлена вниз, то и все слева от нее тоже направлены вниз, а если какая-то направлена вверх, то и все справа от нее тоже направлены вверх. Каждая монета в этой схеме обладает тем свойством, что число монет слева от нее в верхнем ряду плюс число монет справа от нее в нижнем ряду равно 100. Таким образом, 101-я «средняя» монета М характеризуется тем, что слева от нее все стрелки направлены вниз, а справа — вверх.
Найти это место можно с помощью 8 взвешиваний. Вначале перед нами 200 отрезков, на которых еще не расставлены стрелки. Испытываем какой-нибудь отрезок и ставим на нем стрелку. (Если она направлена вниз, то дальше достаточно проверять отрезки справа от нее, а если вверх — то слева: по другую сторону стрелки расставляются автоматически.) Будем проверять каждый раз средний отрезок из непроверенного куска, а если средних два — то один из них. В результате первого испытания останется не больше 100 непроведенных стрелок, в результате 2-го — не более 50, в результате 3-го — не более 25, в результате 4-го — не более 12, в результате 5-го — не более 6, в результате 6-го — не более 3, в результате 7-го — не более 1. 8-е испытание устанавливает направление последней неизвестной стрелки.
Меньшим числом взвешиваний обойтись нельзя. Действительно, перед всеми взвешиваниями все монеты (201) были кандидатами на 101-е место. В результате одного взвешивания множество монет, которые были кандидатами перед этим взвешиванием, делится на два подмножества: те монеты, которые сохранили возможность занять 101-е место, и остальные. Результаты взвешиваний заранее не известны. Поэтому может случиться, что в результате первого взвешивания останется не менее чем 101 кандидат, в результате второго — 51, в результате 3-го — 26, в результате 4-го — 13, в результате 5-го — 7, в результате 6-го — 4, в результате 7-го — 2. Итак, нельзя гарантировать, что число кандидатов после 7 взвешиваний будет меньше 2, что означает, что 7 взвешиваний недостаточно.
Записан