Еще головоломка

[malenkiyscot]

Что-то меня потянуло на головоломки в последнее время. Вот еще одна клевая до чрезвычайности. Если знаете - не подсказывать:

У вас 13 монет. Одна - фальшивая, т.е. имеет другой вес, неизвестно больший или меньший. Найти фальшивую в 3 взвешивания на простых чашечных весах без гирек.

Comments

[avva.livejournal.com]

Откладываем одну монету в сторону. Определяем фальшивую среди 12 оставшихся в 3 взвешивания известным способом; если все три взвешивания будут равными, значит, фальшивая - та, что отложили. Но мы не знаем, легче она или тяжелее (а из 12 - знаем).

[malenkiy-scot.livejournal.com]

С помощью такой логики по индукции можно доказать, что мы можем найти фальшивую среди любого количества монет в 3 взвешивания :). Что напоминает мне следующее:

В академгородке ходят автобусы 1,"K" и "K+1". Доказать, что в академгородке ходят все автобусы.