Question

Перед Алисой лежат в ряд 18 монет, из которых три фальшивые - весят по 4 грамма, а остальные настоящие - весят по 5 грамм. Ещё у Алисы есть весы, показывающие точный вес груза на них. Белый кролик сказал Алисе, что все три фальшивые монеты лежат подряд. Каким наименьшим количеством взвешиваний сможет Алиса найти все фальшивые монеты?

Answer 1

Ответ:   за  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} соответственно.

Получается, Алиса может найти фальшивую монету всего лишь за два взвешивания (за одно у нее это не получится сделать).  

Answer 2

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

Шаг 1: Разделим монеты на три группы по 6 монет в каждой: Группа 1: 1-6 Группа 2: 7-12 Группа 3: 13-18

Шаг 2: Поставим на весы Группу 1 и Группу 2. Сравним их вес.

• Если веса равны, значит, все фальшивые монеты лежат в Группе 3. Переходим к шагу 3.
• Если веса не равны, тогда одна из этих групп содержит одну фальшивую монету. Переходим к шагу 3.

Шаг 3: На этом этапе у нас остается только одна группа, в которой находятся все три фальшивые монеты. Разделим эту группу на три монеты (13-15) и три монеты (16-18).

Шаг 4: Поставим на весы Группу 1 (13-15) и любые две монеты из Группы 2 (16-18).

• Если веса равны, значит, третья монета из Группы 2 является фальшивой. Мы уже знаем, что вес фальшивых монет - 4 грамма, поэтому определение третьей фальшивой монеты необходимо только для подтверждения. Это требует еще одного взвешивания.

• Если веса не равны, то фальшивая монета находится среди монет на весах. Тогда нам нужно еще одно взвешивание (2-е взвешивание) с этими двумя монетами, чтобы выяснить, какая из них фальшивая.

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