Дано 20 баночек с таблетками. В 19 баночках лежат таблетки весом 1 г, а в одной – весом 1.1 г. Даны весы, показывающие точный вес. Как за одно взвешивание найти банку с тяжелыми таблетками?

Решение

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

У нас только одно взвешивание, а это значит, что придется одновременно взвешивать много таблеток. Фактически, мы должны одновременно взвесить 19 банок. Если мы пропустим две (или больше) банки, то не сможем их проверить. Не забывайте: только одно взвешивание!

Как же взвесить несколько банок и понять, в какой из них находятся “дефектные” таблетки? Давайте представим, что у нас есть только две банки, в одной из них лежат более тяжелые таблетки. Если взять по одной таблетке из каждой банки и взвесить их одновременно,то общий вес будет 2.1 г, но при этом мы не узнаем, какая из банок дала дополнительные 0.1 г. Значит, надо взвешивать как-то иначе.

Если мы возьмем одну таблетку из банки №1 и две таблетки из банки №2, то, что покажут весы? Результат зависит от веса таблеток. Если банка №1 содержит более тяжелые таблетки, то вес будет 3.1 г. Если с тяжелыми таблетками банка №2 – то 3.2 грамма. Подход к решению задачи найден.

Можно обобщить наш подход: возьмем одну таблетку из банки №1, две таблетки из банки №2, три таблетки из банки №3 и т.д. Взвесьте этот набор таблеток. Если все таблетки весят 1 г, то результат составит 210 г. “Излишек” внесет банка с тяжелыми таблетками.

Таким образом, номер банки можно узнать по простой формуле: (вес – 210) / 0.1. Если суммарный вес таблеток составляет 211.3 г, то тяжелые таблетки находились в банке №13.

Разбор взят из перевода книги Г. Лакман Макдауэлл и предназначен исключительно для ознакомления.Если он вам понравился, то рекомендуем купить книгу «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию».