Форум умных людей

7

(http://images.samogo.net/images/32423425_world_heaviest_and_biggest_coin_2.jpg)

:angry: :ass: :bad2:

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

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

Расположим золотые монеты в ряд по убыванию масс, серебряные под ними в другой ряд — по возрастанию, и соединим соседние монеты отрезками, как показано на рисунке (в первой строчке монеты золотые, во второй — серебряные).
(http://savepic.ru/4224984.jpg)
Каждый отрезок соединяет две монеты. Придадим ему направление от тяжелой монеты к легкой, так чтобы каждый отрезок превратился в стрелочку. Эти стрелочки обладают тем свойством, что если какая-то направлена вниз, то и все слева от нее тоже направлены вниз, а если какая-то направлена вверх, то и все справа от нее тоже направлены вверх. Каждая монета в этой схеме обладает тем свойством, что число монет слева от нее в верхнем ряду плюс число монет справа от нее в нижнем ряду равно 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 взвешиваний недостаточно.