Comments 2
Задачу с монетами публиковали на Хабре наверно раз 8. Но почему-то всегда описывают пошаговый алгоритм со всеми ветвями. А надо лишь рассмотреть первое взвешивание и его два возможных исхода. Пусть у нас Q(n) = (3^n + 1)/2 монет, и одна настоящая. Взвешиваем (3^(n-1) + 1)/2 монет против (3^(n-1) - 1)/2 + настоящая
1) Весы поровну. Фальшивая среди оставшихся (3^(n-1) + 1)/2 монет, переход к задаче для Q(n-1)
2) Весы накренились. Имеем набор из 3^(n-1) монет, часть из них "предположительно тяжелые" (которые уехали вниз), другая часть - "предположительно лёгкие". Далее такой комплект всегда можно разделить на 3 равные части, так что в двух частях будет A "легких" и B "тяжелых". Эти две одинаковые по пропорциям части сравниваем, если равны то остается третья, если весы накренились, берем "тяжелые" снизу и "легкие" сверху, в любом случае уменьшив число подозреваемых в 3 раза. И т.д.
Лучшие задачи о взвешиваниях монет (шаров, таблеток)