Перед Алисой лежат в ряд 18 монет, из которых три фальшивые - весят по 4 грамма, а остальные настоящие - весят по 5 грамм. Ещё у Алисы есть весы, показывающие точный вес груза на них. Белый кролик сказал Алисе, что все три фальшивые монеты лежат подряд. Каким наименьшим количеством взвешиваний сможет Алиса найти все фальшивые монеты?
Answers & Comments
Ответ: за 2 взвешивания.
Решение:
Пронумеруем все монеты числами от 1 до 18.
Покажем, как можно найти фальшивую монету за два взвешивания.
Сначала взвесим монеты 4, 5, 6, 7, 12, 13, 14, 15. возможны 4 случая:
1. Все монеты весят 40 грамм, то есть среди них нет ни одной фальшивой. Тогда фальшивая монета среди оставшихся. Взвесим 1, 2, 3, 8, 9 монеты. Их вес может быть равен 22 грамма (во взвешивании участвовали 1, 2, 3 фальшивые монеты), тогда фальшивые - 1, 2, 3 монеты. Если вес равен 23 граммам (во взвешивании участвовали 8 и 9 фальшивые монеты), то фальшивые - 8, 9, 10. Если же вес будет равен 24 грамма (участвовала только 9 монета - фальшивая), то все фальшивые - 9, 10, 11 монеты. Если же все монеты весят сколько нужно (25 грамм), то фальшивые - те, которых не взвешивали: 16, 17 и 18 монеты.
2. Масса взвешиваемых монет (4, 5, 6, 7, 12, 13, 14, 15) равна 39 граммов, то есть среди взвешиваемых монет только одна фальшивая. Взвесим монеты 2, 3, 4, 7, 8, 12. Здесь масса может равняться 27 г, 28 г, 29 г и 30 г, а соответствующими тройками 4-граммовых монет будут {2, 3, 4}, {7, 8, 9}, {10, 11, 12} и {15, 16, 17}.
3. Масса взвешиваемых монет равна 38 граммов, среди них уже 2 фальшивые. Теперь взвесим монеты 3, 4, 5, 6, 7, 12, и в случаях, когда весы покажут 27 г, 28 г, 29 г и 30 г, искомыми тройками будут {3, 4, 5}, {6, 7, 8}, {11, 12, 13} и {14, 15, 16} соответственно.
4. Масса взвешиваемых монет (4, 5, 6, 7, 12, 13, 14, 15) равна 37 граммам, на весах все три фальшивые монеты, которые надо найти. Теперь взвесим на весах всего лишь 4 детали: 4, 5, 6, 12. В зависимости от того, равна она 17 г, 18 г, 19 г или 20 г, искомой тройкой монет будет {4, 5, 6}, {5, 6, 7}, {12, 13, 14} или {13, 14, 15} соответственно.
Получается, Алиса может найти фальшивую монету всего лишь за два взвешивания (за одно у нее это не получится сделать).