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