Мудрая Сова и 5 монет

[Ktina]

Перед Мудрой Совой выложили 5 монет. Сова точно знает, что ровно две из этих монет - фальшивые, причём одна фальшивая монета тяжелее настоящей, а другая - легче.
Задача Совы - обнаружить обе фальшивые монеты за 3 взвешивания на чашечных весах без гирь.
Но есть два момента. Во-первых, ни на какую чашу весов нельзя класть две или более монет одновременно. Во-вторых, все три взвешивания должны быть спланированы заранее, то есть, последующие взвешивания не должны зависеть от результатов предыдущих (говоря языком программистов, код должен быть без ифов).

Помогите Сове!

[venco]

А почему вы решили, что это возможно?

[Dmitriy40]

По моему тоже невозможно: если нигде не ошибся, то есть всего 4 варианта топологии последовательностей взвешивания и для всех них у меня построены контрпримеры распределения монет, когда не удаётся определить обе фальшивых монеты.

[Ktina]

venco в сообщении #1321246 писал(а):

А почему вы решили, что это возможно?

Задача - не моя, мне её прислали по почте. Возможно, под помощью Сове имелось в виду либо дать ей нужный алгоритм, либо доказать, что его нет.

[TOTAL]

Мудрая сова не использует слово "если":

1) первую сравниваем со второй
2) третью сравниваем с четвертой
3) пятую сравниваем с настоящей

[wrest]

TOTAL
1) первую сравниваем со второй : перевесила первая
2) третью сравниваем с четвертой : перевесила третья
3) пятую сравниваем с настоящей : пятая оказалась настоящей
и?

[TOTAL]

Вот на языке программирования:

$v1=sign(a(1)-a(3))$
$v2=sign(a(2)-a(4))$
$v3=sign(a(5)-a(2+v2))$

По значениям $v1, v2, v3$ находим фальшивки

[kotenok gav]

У вас третье взвешивание зависит от результата второго.

[TOTAL]

kotenok gav в сообщении #1321284 писал(а):

У вас третье взвешивание зависит от результата второго.

Все мои взвешивания спланированы заранее, код без ифов, как требовалось. Или автору придется уточнить, что такое "взвешивания спланировать заранее".

[Dendr]

Если я правильно понимаю, то сова нумерует монеты от 1 до 5, потом составляет таблицу из трех строк, в первом столбце пишет пары цифр, а во втором будут фигурировать результаты взвешивания - всего 27 исходов, при 20 вариантах распределения. На этом этапе пока взвешиваний хватает...

Конечно, при таком подходе порядок взвешиваний неважен, и мы можем их переставлять в плане. При этом очевидно, что хотя бы одна из монет участвует во взвешиваниях дважды (Дирихле). Пусть для определенности то номер 1 (опять же, до начала взвешивания мы можем перенумеровывать их как угодно), и она сравнивается сначала с 2, потом с 3. Всего 9 исходов, но нам интересен, в частности, случай, когда она тяжелее их обеих.
Следовательно, она - тяжелая, а легкая - среди четырех остальных. Еще одним взвешиванием мы можем различить три варианта, но никак не 4. Таким образом, сове никак не удастся совершить задуманное.

Но все же оценим шансы совы. Все же 9 исходов!
1) Если 1=2, 1=3, то это все настоящие монеты, тогда фальшивки уже найдены. Сравнение 4 и 5 позволит их различить.
2) Если 1=2, 1>3 - первые настоящие, 3 - легкая фальшивка. Тяжелая - либо 4, либо 5. Сравнив их между собой, мы различим тяжелую от настоящей.
3-5) 1=2, 1<3; 1>2, 1=3; 1<2, 1=3 - эти исходы аналогичны (2) с точностью до нумерации и терминологии веса.
6) 1>2, 1<3 - легко понять, что 3 - тяжелая фальшивка, 2- легкая, а 1 - настоящая. Третье взвешивание не понадобится, поэтому без разницы, как его провести.
7) 1<2, 1>3 - симметричен исходу (6)
8) 1>2, 1>3. Как указано выше, 1 - тяжелая. И раз уж нам понравилось взвешивать 4 и 5, то так и поступим. При разности весов мы находим легкую фальшивку. Но при равенстве... выходит, что среди монет 2 и 3 одна фальшивая легкая и одна настоящая, но какая из них, мы выяснить не сможем.
9) 1<2, 1<3 - аналогично (8), но легкая и тяжелая монеты меняются местами в рассуждениях.

Итак, при самом удачном планировании (взвесить 1-2, 1-3, 4-5) мы не сможем различить варианты ТЛННН и ТНЛНН, а также ЛТННН и ЛНТНН, хотя одна из монет локализуется полностью. Все остальные (всего 16) позволяют найти обе монеты. 80% успеха - это уже что-то.

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