|
|
 |
Условие
Банкир узнал, что среди одинаковых на вид монет одна — фальшивая (более легкая). Он попросил эксперта определить эту монету с помощью чашечных весов без гирь, причем потребовал, чтобы каждая монета участвовала во взвешиваниях не более двух раз. Какое наибольшее число монет может быть у банкира, чтобы эксперт заведомо смог выделить фальшивую за n взвешиваний?Решение
Решим сначала более простую задачу. Пусть банкир разрешает класть на весы монеты не более 1 раза. Из какого наибольшего числа монет можно выделить более легкую за k взвешиваний?Если при каком-то взвешивании на чаше весов будет больше одной монеты, то из них выделить фальшивую монету не удастся (второй раз взвешивать монету нельзя!). Поэтому при каждом взвешивании на чаши кладется по одной монете.
Если весы не в равновесии, то фальшивая монета очевидна. А если в равновесии, то количество подозрительных монет уменьшится на 2. Следовательно, при k взвешиваниях можно выделить фальшивую из 2k + 1 монет.
Возвращаясь к исходной задаче, обозначим ответ в ней через f (n). Пусть при
первом взвешивании на чашах лежат по s монет. Если весы окажутся не в
равновесии, то придется искать фальшивую монету среди s монет, причем каждую
из них можно использовать лишь по одному разу, и осталось n - 1 взвешивание. По
доказанному
s2(n - 1) + 1 = 2n - 1.
Если весы в равновесии, то получаем исходную задачу для монет, не попавших на весы (их f (n) - 2s), и n - 1 взвешивания, значит,
Следовательно,
С другой стороны, если имеется 2n2 + 1 монет и каждый раз брать s максимальным, т. е. на первом шаге s = 2n - 1, на втором — s = 2n - 3, и т. д., то эксперт сможет выделить фальшивую монету. Значит, f (n) = 2n2 + 1.
