Олимпиадная задача: Найдите фальшивую монету за n взвешиваний с ограничениями

  Решим сначала более простую задачу. Пусть банкир разрешает класть на весы монеты не более 1 раза. Из какого наибольшего числа монет можно выделить более легкую заk взвешиваний? Если при каком-то взвешивании на чаше весов будет больше одной монеты, то из них выделить фальшивую монету не удастся (второй раз взвешивать монету нельзя!). Поэтому при каждом взвешивании на чаши кладется по одной монете.

Если весы не в равновесии, то фальшивая монета очевидна. А если в равновесии, то количество подозрительных монет уменьшится на 2. Следовательно, при k взвешиваниях можно выделить фальшивую из 2k + 1 монет.

Возвращаясь к исходной задаче, обозначим ответ в ней через f (n). Пусть при первом взвешивании на чашах лежат по s монет. Если весы окажутся не в равновесии, то придется искать фальшивую монету среди s монет, причем каждую из них можно использовать лишь по одному разу, и осталось n - 1 взвешивание. По доказанному s$\le$2(n - 1) + 1 = 2n - 1.

Если весы в равновесии, то получаем исходную задачу для монет, не попавших на весы (их f (n) - 2s), и n - 1 взвешивания, значит,

Отсюда Следовательно, Поскольку, как легко проверить,f(1) = 3, имеемf(n)$\le$2n²+ 1 по формуле для суммы арифметической прогрессии. С другой стороны, если имеется 2n² + 1 монет и каждый раз брать s максимальным, т. е. на первом шаге s = 2n - 1, на втором — s = 2n - 3, и т. д., то эксперт сможет выделить фальшивую монету. Значит, f (n) = 2n² + 1.

Ответ задачи отсутствует