Имеется 12 монет, одна из них фальшивая, но неизвестно, легче она или тяжелее обычной...

Question

Имеется 12 монет, одна из них фальшивая, но неизвестно, легче она или тяжелее обычной монеты.
Как за 3 взвешивания найти фальшивую монету и определить, легче она или тяжелее?
Дополнительный вопрос повышенной трудности:
А если монет 13, как найти фальшивую за те же 3 взвешивания, но уже определять легче она или тяжелее не обязательно?

Comments

Есть даже программа, которая решает это. Типичная задача по программированию. Алгоритм через n log n

Answer 1

1) Сразу замечание - фальшивая МОНЕТА всегда ЛЕГЧЕ подлинной.
Кто же станет чеканить монеты себе в убыток.
2) На равноплечих весах можно получить не два результата - равно или не равно, а три: меньше, равно или больше. Это следует учитывать в алгоритме расчета.
3) Делая выбор какую чашу весов  взять для второго взвешивания (тяжелую или лёгкую)  мы делаем (в уме) ещё одно взвешивание. Наш выбор может стать правильным и не надо будет делать ещё одно взвешивание.
РЕШЕНИЕ
Для начала монеты обозначим - м.
Первое взвешивание - отложили - 4м
4м = 4м  + 4м (отложены)
1) ДА - равно - все 8м на весах  становятся   подлинными - 8П + 4м
Второе взвешивание -  3П = 3м + м (отложена)
ДА - равно - отложена - м - одна штука. 
Третье взвешивание - П ≠ м - узнаем легче она или тяжелее. - КОНЕЦ.
2) НЕТ - была отложена подлинная группа и она становится - 4П.
Важно для второго взвешивания  одновременно запомнить какую из неравных групп мы выбираем - "легкую" или "тяжелую".
Вопреки моему замечанию выберем "тяжелые" - 4м+ - вдруг фальшивая окажется тяжелой.
Второе взвешивание - 4м+ - одну монету откладываем и взвешиваем
3П = 3м  + м (отложена)
ДА - равно - 3П=3П и отложена - м+ - и фальшивая и тяжелая - КОНЕЦ.
НЕТ - на этот раз однозначно выбираем "легкую" группу - 2Пм
Третье взвешивание -  одну монету, как всегда откладываем.
П = П + м-(отложена) фальшивая и легкая- КОНЕЦ
П >м-   + П - фальшивая и легкая на весах. - КОНЕЦ.  
В приложении набросок алгоритма решения задачи.

---