олимпиада - Задача на взвешивания

Для начала, отметим, что класть на весы разное количество монет абсолютно бесполезно. Значит, единственный способ решения задачи - на каждом шаге делить все монеты на три группы размерами $%i, i, n-2i$% (где $%n$% - число монеток) и класть на весы первые две группы, что однозначно покажет, в какой из трех групп находится фальшивая монетка.
Сначала решим более простую задачку: из скольки монет (максимум) можно найти фальшивую за $%m$% взвешиваний, если каждую монету можно класть на весы только один раз? Из-за такого строгого ограничения есть только один способ нахождения фальшивой монетки: класть на весы по две монетки за шаг ($%i=1$%). Следовательно, за $%m$% взвешиваний мы сможем найти фальшивую монетку в группе максимум из $%2m+1$% монеток.
Вернемся к исходной задаче. Если мы хотим найти фальшивую монетку в группе из $%n$% монеток за $%m$% взвешиваний, то оптимальным алгоритмом будет сравнить на первом шаге группы из $%i=2m-1$% монеток. Если одна из групп легче, то в ней фальшивая монетка, которую нам надо найти за $%m-1$% взвешиваний. В предыдущем абзаце доказано, что это возможно. Если же весы уравновешены, то фальшивая монетка находится в третьей группе, и мы повторяем тот же алгоритм для новых параметров: $%n_{i+1}=n_i-2(2m-1), m_{i+1}=m_i-1$%. Итак:
$%n_0=99;m_0=7$%
$%n_1=99-2(2 \times 7-1)=73;m_1=6$%
$%n_2=73-2(2 \times 6-1)=51;m_2=5$%
$%n_3=51-2(2 \times 5-1)=33;m_3=4$%
$%n_4=33-2(2 \times 4-1)=19;m_4=3$%
$%n_5=19-2(2 \times 3-1)=9;m_5=2$%
$%n_6=9-2(2 \times 2-1)=3;m_6=1$%
$%n_7=3-2(2 \times 1-1)=1;m_7=0$%
То есть, после седьмого взвешивания в третьей группе осталась ровно одна монетка, которая и является фальшивой. То есть, ответ - да, можно.
P.S. у меня есть доказательство оптимальности алгоритма, который я использовал выше, но его я приводить здесь не буду, т.к. формально цель достигнута - найден способ. А вот если бы монеток было 100, то пришлось бы писать, чтоб доказать, что способа нет...