Взвешивания и количество информации

Предположим противное — пусть существует алгоритм, позволяющий найти фальшивую монету из монет за ходов.

Любой алгоритм можно закодировать в виде дерева, которое строится следующим образом. На первом уровне находится одна вершина-корень, соответствующая первому взвешиванию. Из нее исходит три ребра на второй уровень, соответствующие различным результатам этого взвешивания: и Аналогично выстраиваются и последующие уровни: на уровне с номером находится вершин. На каждой указано, какое взвешивание в ней совершается, и из каждой вершины исходит по ребра на уровень соответствующие всевозможным результатам этого взвешивания.

Легко заметить, что в любом таком дереве листьев, и каждый лист соответствует некоторой последовательности из взвешиваний. После взвешиваний мы обязаны определить, какая из монет является фальшивой. Занумеруем монеты и запишем на каждом листе номер монеты, на которую он указывает.

Выберем произвольную монету с номером и предположим, что она фальшивая. Тогда в дереве алгоритма обязательно должны присутствовать листья:

Которые соответствуют случаю, когда все взвешиваний были сделаны правильно. Ясно, что такой лист только один;

Которые соответствуют случаю, когда одно из взвешиваний было выполнено неверно. Таких листьев ровно Они могут быть получены из пути к листу в пункте если с него свернуть в произвольной вершине, а все остальные взвешивания выполнить правильно;

Которые соответствуют случаю, когда два взвешивания были выполнены неверно. Аналогично, такие листья могут быть получены из пути к листу в пункте если с него свернуть в произвольной вершине, и далее все, кроме одного, взвешивания провести верно. Любой такой лист характеризуется выбором двух позиций, на которых взвешивание произведено неверно, а также выбором одного из двух неверных результатов, поэтому их количество равно

Итак, если монета фальшивая, то в дереве алгоритма должно быть хотя бы листьев, которые на нее указывают. Перестановкой монет можно добиться, чтобы фальшивая монета имела любой номер от до поэтому листьев должно быть хотя бы С другой стороны, известно, что листьев ровно откуда следует неравенство и Это противоречит условию задачи, по которому значит предположение о противном в начале решения было не верным.