КТО СОБИРАЕТСЯ ДОКАЗАТЬ, ЧТО 101-Ю МОНЕТУ МОЖНО ОПРЕДЕЛИТЬ ЗА 7-8 или даже 16 ВЗВЕШИВАНИЙ - чтож (есстественно соблюдая условия поставленные в задаче)
ФЛАГ В РУКИ БАРАБАН НА ШЕЮ И СТРАУСИНОЕ ПЕРО В ЗАДНИЦУ- ВПЕРЕДмогу ещё предложить - паровоз навстречу
Вдохновившись сим оптимистическим напутствием, приводится попытка доказательства.
Показать скрытый текст Рассмотрим более общую ситуацию: имеется g золотых монет, упорядоченных по возрастанию массы, s серебряных монет, также упорядоченных по возрастанию массы и мы ищем k-ю по тяжести монету в общем упорядочении всех имеющихся монет. Докажем, что за одно взвешивание мы можем перейти к ситуации с параметрами g', s', k/2, если k чётное, и g', s', [k/2] + 1, если k — нечётное. Для этого сравним [k/2]-е монеты в золотом и серебряном рядах. Без ограничения общности полагаем, что золотая монета тяжелее. Но тогда легче [k/2]-й серебряной монеты может быть лишь ([k/2] – 1) + ([k/2] – 1) ≤ k – 2 монет, значит, серебряные монеты от первой до [k/2]-й можно отбросить. Искомая монета будет теперь иметь номер k/2 при чётном k и [k/2] + 1 — при нечётном, что и требовалось доказать.
Возможен случай, когда в одном из рядов меньше [k/2] монет. Тогда аналогичным рассуждением убеждаемся, что из другого ряда можно выбросить [k/2] монет.
Перед началом взвешиваний имеем: g = 101, s = 100, k = 101. После 1-го взвешивания: k = 51, после 2-го взвешивания: k = 26, после 3-го взвешивания: k = 13, после 4-го взвешивания:
k = 7, после 5-го взвешивания: k = 4, после 6-го взвешивания: k = 2, после 7-го взвешивания: k = 1.
Итак, перед 8-м взвешиванием нам нужно найти самую лёгкую монету. Это легко сделать, сравнив по весу самые лёгкие монеты из двух рядов. Таким образом, 8 взвешиваний достаточно.
Докажем, что меньшим числом взвешиваний обойтись нельзя. Для этого будем смотреть, как меняется в результате взвешивания число подозрительных монет, которые могут оказаться 101-ми по счёту. Вначале подозрительных монет 201, поскольку любая может оказаться 101-й. В результате взвешивания отпадает какое-то множество монет, причём каждая монета может быть исключена из числа подозрительных лишь при одном из результатов взвешивания, либо ни при каком из результатов взвешивания на этом шаге, так как иначе её можно было бы исключить из числа подозрительных монет до этого шага. Но это означает, что при каждом результате взвешивания число подозрительных монет сократится не более чем на половину. Поскольку 27 = 128 < 201, необходимо по крайней мере 8 взвешиваний.
Записан