Олимпиадная задача по теории алгоритмов: разделение 32 и 22 монет на равные кучки

  а) При каждом взвешивании будем класть на весы все 32 монеты. Изначально у нас есть одна куча, в которой есть две фальшивые монеты. Сделаем из неё пару вдвое меньших куч и разложим их на разные чаши весов. Если фальшивки попали в разные кучи, то будет равновесие (и задача решена), а при неравновесии мы знаем, что обе фальшивки оказались в одной и той же куче. Снимем кучи с весов и удвоим их количество, разбив каждую старую кучу на пару новых. При следующем взвешивании будем класть половинки одной кучи на разные чаши. Снова при неравновесии мы знаем, что фальшивки оказались в одной куче. Так мы делаем четыре взвешивания: при первом на каждой чаше одна куча из 16 монет, при втором – две по 8 монет, при третьем – четыре по 4, при четвёртом – восемь по 2. По тому же принципу разложим монеты на чаши для пятого взвешивания, только проводить его не надо: на этот раз фальшивки наверняка на разных чашах, значит, должно наступить равновесие.   б) Первый способ. Как и в а), будем взвешивать каждый раз все монеты и перед каждым взвешиванием удваивать число куч, деля каждую старую на пару новых. Метод потребует лишь небольшого уточнения. А именно, если в старой куче число монет нечётно (например, 11), то делим её "почти пополам": так, чтобы число монет в "половинках" отличалось на единицу  (11 = 5 + 6).  При этом из первой нечётной кучи положим меньшую половинку на левую чашу, а большую – на правую, со второй нечётной кучей поступим наоборот и т.д. Поскольку число нечётных куч чётно, на чашах окажется поровну монет.

  В результате при первом взвешивании у нас будут на каждой чаше кучи по 11, при втором –  5 + 6,  при третьем –  2 + 3 + 3 + 3,  при четвёртом –

1 + 1 + 1 + 2 + 1 + 2 + 1 + 2;  в случае четырёх неравновесий обе фальшивки по-прежнему оказываются в одной куче, и после последнего взвешивания их можно будет гарантированно разложить по разным чашам.   Второй способ. Отложив одну монету, разделим оставшиеся на три кучки по 7 монет. Легко видеть, что, где бы ни находились фальшивые монеты, две из этих трёх кучек будут одного веса, а третья – другого. Достаточно двух взвешиваний, чтобы определить, какие именно две кучки имеют одинаковый вес.

  Добавляя к третьей кучке оставшуюся монету, получаем кучку из восьми монет (она либо содержит обе фальшивые монеты, либо ни одной). Из а) ясно, как не более чем за два взвешивания разделить её на две кучки равного веса.

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