8 монет и три взвешивания

           8 монет и три взвешивания
        Вечером говорил с человеком, который утверждал, что может выделить из 12 монет фальшивую тремя взвешиваниями. Я ему не поверил. Обратились к Интернету. Там такая жуткая переписка по проблеме взвешивания, что я решил опубликовать моё видение этой задачи. Задача существует помимо нас и живёт своей жизнью, следовательно и алгоритм, который не зависит от нас, тоже существует.
        Разберём подробно более простой случай, в котором только 4 монеты, среди которых одна обладает другим весом.
        Решение. Раскладываем их на 4 кучки - по одной монете в каждой. Берём первые две монеты и помещаем их на весы. Если их веса неравны, то одна из них фальшивая, а обе не взвешенные - настоящие. При помощи одной из настоящих монет за одно взвешивание выделяем фальшивую (если веса равны, то фальшивая осталась лежать на столе, но мы не знаем тяжелей она или легче, чтобы ответить на этот дополнительный вопрос, требуется дополнительное взвешивание); если веса не равны, то фальшивая монета на весах и в этом случае мы знаем тяжелей она или наоборот легче настоящей.
        Когда я знаю "легче или тяжелей", каждое отклонение стрелки от среднего положения позволяет выделить фальшивую из 4-х куч за одно взвешивание. Поэтому при массовом решении этой задачи имеет смысл на первом же шаге выяснить легче фальшивая или тяжелей. Однако при одноразовом решении задачи это увеличит число взвешиваний на 1, потому что в худшем случае событие неравенства весов обладает правом не наступать до самого конца (фальшивая монета не попадает на весы, оставаясь на столе до самого конца).
        Общий случай - 8 или "два в степени эн". Раскладываем монеты на 4 кучи (для 8 по две в каждой) - одна из куч содержит фальшивую монету. Значит за два взвешивания мы можем выделить кучу, содержащую фальшивую монету. Получается, что за два взвешивания из 8 монет мы выделяем кучу с фальшивой монетой (на столе осталась только четверть монет и в худшем случае мы не знаем тяжелее она или легче. Иными словами, перед нами та же самая задача только с четвертью монет, (в худшем случае при каждом взвешивании будет наблюдаться только равенство весов).
        Тут изложено не только решение, но и одновременно доказательство, что за меньшее число взвешиваний задача не решается, как только стрелка на весах впервые отклоняется, число взвешиваний сокращается на единицу. Воспользоваться тем, что стрелка весов может занимать три положения, отклоняясь вправо, влево или не отклоняясь вовсе, - в рассматриваемой задаче не получится.
        Осталось подсчитать взвешивания. Первыми двумя взвешиваниями я выделил: 2 из 8-ми, 4 из 16 и 8 из 32 монет, тогда как все остальные - подлинные. Пользуясь подлинными монетами, я за одно взвешивание выделяю фальшивую из двух
монет (итого 3 взвешивания); за два взвешивания выделяю одну монету из 4 (в итоге: 4 взвешивания для 16 монет); и за 3 взвешивания - одну монету из 8 для случая 32 монет (итог: 5 взвешиваний).