Задача о двух милиционерах

Добрый день.

Многие помнят из детского сада школы теорему о двух милиционерах (название которой, видимо, объясняется тем, что если два милиционера идут в отделение, держа между собой преступника, то совершенно точно известно, куда идёт арестованный). Теорема важная и полезная, позволяет много хорошего понять про последовательности и функции, но сегодня мы поговорим не о ней (впрочем, желающие найдут подробности в википедии), а о задачке про 10 монет и весы. Раньше мы уже решали несколько простых задач о взвешиваниях. А сейчас будет более интересная.

В одной маленькой-маленькой стране был только один вид монет (все они выглядели и весили одинаково). Но коварные соседи научились изготавливать фальшивые деньги (на вид неотличимы от настоящих, но имеют больший вес). Нам повезло, так как враг хоть и коварен, но аккуратен — все фальшивые монеты заведомо имеют одинаковый вес.

Теперь ситуация: у вас в кармане есть ровно девять монет, причём вы уверены, что все они настоящие. На эти деньги вы покупаете, например, ароматный арбуз. Но торговец почему-то усомнился, не фальшивы ли ваши деньги, поэтому вызвал милицию.

Вам повезло, так как у торговца есть рычажные весы (т.е. весы с двумя чашами), а милиционеры согласны позволить вам сэкономить время, прямо на месте воспользовавшись этими весами, чтобы доказать свою честность (показать, что все монеты настоящие). Но есть одна проблема: весы очень ветхие, поэтому вы можете воспользоваться ими всего три раза (на четвёртый раз они сломаются, а вот три раза отработают правильно). Вам повезло ещё больше, ведь у милиционеров есть образец фальшивой монеты, который они любезно позволили использовать для доказательства (чтобы не перепутать с остальными монетами, на нём фломастером написали букву «Ф»).

Итак, вопрос: как выяснить за три взвешивания, есть ли среди ваших девяти монет фальшивая, пользуясь ещё одной заведомо фальшивой монетой?

Автор этой задачи А. В. Шаповалов, а сама она достаточно свежая (засвечена, насколько я помню, всего около двух лет назад).

Дополнение: в таких задачах предполагается, что весы умеют показывать, какая чаша тяжелее, но не показывают разницу масс объектов, находящихся в чашах. Другими словами, весы выдают знак (один из трёх ответов: «левая чаша тяжелее», «правая чаша тяжелее» или «чаши имеют одинаковый вес»), но не абсолютное значение.

Приглашаю обсудить задачу в комментариях. И покажите, пожалуйста, ссылку на эту задачку (http://my-tribune.blogspot.com/2012/08/9-monet.html) своим знакомым, любящим поломать голову :)

Хорошего дня!