Question

Имеется 10 мешков с монетами, в девяти из них настоящие монеты весом в 10 г, а в одном фальшивые весом 9 г. Есть весы, показывающие общий вес положенных на них монет. Как с помощью одного взвешивания найти мешок с фальшивыми монетами?

Answer 1

9*10=90 грамм монет, 90+9=99 общий вес всех монет

Answer 2

Для решения этой задачи можно взвесить по одной монете из первого мешка, две монеты из второго мешка, три монеты из третьего мешка и так далее до десяти монет из десятого мешка.

Таким образом, общее количество взвешиваний будет равно:

1 + 2 + 3 + ... + 10 = 55

Но этот способ требует 55 взвешиваний, что довольно затратно по времени. Существует более быстрый метод, основанный на бинарном поиске.

Для этого сначала разделим 10 мешков на две группы по 5 мешков в каждой группе. Положим на весы все 5 мешков первой группы. Если общий вес монет на весах соответствует весу 50 г (10 г × 5 монет), то фальшивые монеты находятся во второй группе мешков. Если же общий вес монет на весах меньше 50 г, то фальшивые монеты находятся в одном из мешков первой группы.

Далее разделим группу с подозрительными мешками на две группы по 2 мешка в каждой группе и оставшийся мешок отложим в сторону. Положим на весы два мешка из первой группы. Если общий вес монет на весах соответствует весу 20 г (10 г × 2 монеты), то фальшивые монеты находятся в оставшемся мешке. Если общий вес монет на весах меньше 20 г, то фальшивые монеты находятся в одном из мешков второй группы.

Наконец, положим на весы оставшиеся два мешка. Если общий вес монет на весах соответствует весу 20 г (10 г × 2 монеты), то фальшивые монеты находятся в одном из этих двух мешков. Если же общий вес монет на весах меньше 20 г, то фальшивые монеты находятся в оставшемся мешке.

Таким образом, мы можем найти мешок с фальшивыми монетами, проведя всего три взвешивания.