Решим ещё одну задачу с тестированием чего-нибудь на мышах! Или на весах! Ещё одна задача из арсенала принимающих на работу и просто правильная гимнастика для мозга. Теперь условия такие:
- есть 20 баночек с таблетками;
- в одной из них отравленные таблетки;
- таблетки из настоящих банок весят по 1 грамму;
- таблетки из одной отравленной банки — 1,1 грамма;
- все банки выглядят одинаково внутри и снаружи;
- есть очень точные весы, на которых можно взвешивать что угодно в любом количестве.
Как за одно взвешивание найти банку с токсичными таблетками?
У нас в распоряжении есть только одно взвешивание. Это значит, что надо найти такой алгоритм, который сразу даст точный и однозначный ответ.
Если мы положим на весы одну нормальную таблетку, они покажут 1 грамм, а если испорченную — 1,1 грамма. Давайте посмотрим, что будет, если из каждой банки мы возьмём по одной таблетке и положим их все на весы:
(19 × 1) + (1 × 1,1) = 20,1.
Отсюда можно сделать два важных вывода:
- нельзя брать одинаковое количество таблеток из каждой банки, потому что тогда мы не отличим банки друг от друга;
- одна испорченная таблетка даёт лишний вес в 0,1 грамма.
Раз нужно из каждой банки брать какое-то своё количество таблеток, попробуем сделать так:
- из первой банки возьмём 1 таблетку;
- из второй банки — 2 таблетки;
- …
- из двадцатой банки — 20 таблеток.
По этой схеме у нас получится всего:
1 + 2 + 3 + … + 19 + 20 = 210 таблеток.
Теперь нам нужно учесть лишний вес в 0,1 грамма, который даёт каждая испорченная таблетка. Получается, что если у нас будет одна такая, то лишний вес составит 0,1 грамма, если две — 0,2 грамма и так далее. Зная общее количество лишнего веса, можно будет вычислить количество испорченных таблеток:
количество испорченных таблеток = лишний вес / 0,1.
Осталось найти лишний вес. Для этого возьмём 210 таблеток по нашей схеме, взвесим их, а от результата отнимем 210 — вес всех таблеток, если бы они были нормальными и весили по одному грамму каждая.
Как это работает на практике
Например, у нас отравлена банка № 14. Раз мы берём из неё по схеме 14 таблеток, которые в сумме весят 14 × 1,1 = 15,4 грамма, то общий вес всех таблеток получится:
196 + 15,4 = 211,4 грамма.
Найдём лишний вес:
211,4 – 210 = 1,4 грамма.
Теперь разделим его на 0,1, чтобы узнать номер отравленной банки:
1,4 / 0,1 = 14.
Как видите, такой способ действительно позволяет за одно взвешивание найти нужную банку с таблетками.
Ни одной мыши не пострадало!
