выложены 28 одинаковых по внешнему виду монет. среди них есть две рядом лежащие фальшивые монеты более тяжёлые. найти за 3 действия фальш.

18 человек оценили этот вопрос
Интересный вопрос
Лучший ответ

Оригинально это задача была представлена на конкурсе им. Савина в журнале Квант #4 в 2006 году. В такой формулировке:

В ряд выложены 28 одинаковых по внешнему виду монет. Среди них есть две рядом лежащие фальшивые монеты — более тяжёлые, чем настоящие. Можно ли за 3 взвешивания на чашечных весах без гирь найти фальшивые монеты?

Решения в интернете я не нашёл, поэтому приведу своё решение. Любая задача на взвешивание монет на каждом шаге даёт 3 варианта: тяжелее, легче или равны. В самом сбалансированном случае это означает принадлежность искомого объекта к одной из кучек, большая из которых не может быть меньше, чем 1/3 от размера исходного числа монет. Тогда поиск одной монеты за 3 взвешивания осуществим только для 3^3=27 монет (или меньше).

В нашей постановке задачи есть дополнительная информация о том, что пара монет лежит рядом, поэтому мы будем искать позицию пары. Таких позиций будет ровно 27 (1-2, 2-3, ..., 27-28) -- значит у нас всё может получиться!

Разделим монеты на 3 кучки по 10 штук с перекрытием в одну монету: 1-10, 10-19, 19-28, и попробуем определить принадлежность нашей пары к одной из этих кучек. Для этого взвесим на весах первые 9 монет (1-9) и последние 9 (20-28). Если они равны, в них нет фальшивых монет, а обе тяжёлые монеты принадлежат средней кучек из 10 монет (10-19). Если одна из них окажется тяжелее, это значит, что 1 или 2 тяжёлые монеты попали в неё. Мы знаем, что тяжёлые монеты ходят парами, поэтому мы гарантируем, что обе попадут в "расширенную" кучку (1-10) или (19-28).

Теперь у нас есть кучка из 10 монет, в которой прячется фальшивая пара. Повторим процедуру для 3 кучек размером 4 монеты с перекрытием: 1-4, 4-7, 7-10. Взвесим 1-3 и 8-10 и найдём четвёрку, в которой скрывается наша пара монет, по тому же принципу.

Последний шаг - найти пару среди 4 монет. Взвесим крайние 1 и 4. Если равны - пара посередине, если 1я тяжелее, то фальшивые 1-2, если легче - 3-4.

172

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

1
Написать комментарий
Ещё 3 ответа

Монеты , не банкноты . Фальшивые не бывают , а бывают редкие.

Цена редких монет намного выше обычных (не по сибестоимости) ,

т.к. тираж их намного ниже.

16
Написать комментарий
Мы скрыли 2 ответа, потому что они противоречат правилам сервиса.Показать

0/140Ответ не может быть меньше 140 символов