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

[malenkiyscot]

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

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

Comments

[amigofriend.livejournal.com]

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

[malenkiy-scot.livejournal.com]

Хорошо. Тогда специально для тебя: каково максимальное количество монет из которых можно найти одну фальшивую тремя взвешиваниями? Докажи.

[ait.livejournal.com]

Ответ - 13
Доказательство - иначе в условиях головоломки было бы именно это число.

[malenkiy-scot.livejournal.com]

Браво! Хотя в изначальной головоломке - 12, т.к. для 13-ти решение немного кривое.

[malenkiy-scot.livejournal.com]

Ну что, забьем болт или давать решение?

[avva.livejournal.com]

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

[malenkiy-scot.livejournal.com]

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

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