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

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