Кстати! Вот кажется решение!!!
1. Делим все монеты на 3 части. Треть откладываем, треть взвешиваем (разделив пополам). 2. Если равенство (с вероятностью 1/3), то мы понизили порядок задачи втрое за 1 взвешивание. Если неравенство, то в полтора раза понизили. 3. Теперь с обеих чашек весов снимаем по 1/3 монет и откладываем (не перемешивая). Оставшиеся монеты делим пополам (на каждой чашке) и половины меняем с другой чашкой весов. 4. Если равенство, то мы опять понизили порядок задачи втрое. Если неравенство осталось прежним, то можно отбросить отложенную треть и перенесенные монеты с одной чашки на другую, что в сумме дает еще треть! Т.о. порядок задачи опять уменьшается втрое. Если знак неравенства поменялся на противоположный, то остаются только перемещенные монеты, а их опять же 1/3 и опять порядок задачи уменьшается втрое! Итак, начиная со второго взвешивания, порядок задачи с каждым разом уменьшается втрое! Итак, для N монет нам надо log3 N взвешиваний! И нам плевать, знаем ли мы что фальшивка тяжелее или легче! Однако, это справедливо только для больших N, т.к. при малых, мы стоклкнемся с тем, что число монет нацело не делится на 3 и придется округлять.
|