Среди 12 настоящих монет есть две фальшивые. они одинаковые по весу но легче настоящих. за какое наименьшее количество взвешиваний можно гарантировано найти фальшивые монеты? (методом "проб и ошибок" можно понять что ответ-5,я не знаю как это доказать, ! )
ответ:
всего лишь 3
пошаговое объяснение:
пронумеруем монеты числами от 1 до 12. взвесим монеты 1—4 с монетами 5—8.
1) если весы в равновесии, то все монеты на них настоящие. взвесим с
если весы и сейчас в равновесии, то фальшивая — 12 и, взвешивая ее с 1, определим, легче она или тяжелее.
если же равновесия нет, то фальшивая среди монет 9—11, и мы знаем ее тип (легче она или тяжелее). из трех монет можно найти фальшивую за одно взвешивание (см. пункт а)
2) если одна чашка перевесила. пусть, например, это чашка 1—4. тогда либо одна из них тяжелее настоящих, либо одна из 5—8 легче настоящих.
взвесим 1, 2, 5 и 3, 4, 6.
если весы в равновесии, то взвесим 7 и 8 — фальшивая та из них, которая легче.
если одна чашка перевесила, то пусть, например, это чашка 1, 2, 5. это означает, что фальшивая либо 1 либо 2 (тяжелее настоящей), либо 6 (легче настоящей). взвешивая 1 и 2, мы определим, какая ситуация реализовалась.
докажем, что за 2 взвешивания сделать этого нельзя. допустим, есть такой алгоритм. при его выполнении может произойти 9 вариантов (3 результата первого взвешивания и в каждом из них три результата второго взвешивания). по этим вариантам мы должны назвать фальшивую монету однозначно. но поскольку монет 12, то какую-то из них наш алгоритм никогда не назовет фальшивой. значит, если именно она фальшивая, алгоритм даст неправильный ответ