"Есть 12 одинаковых внешне монеток. Одна из них фальшивая - либо легче, либо тяжелее. Нужно за три взвешивания на обычных весах найти фальшивую и сказать, она легче или тяжелее."
делим на 3 кучки по 4 монеты
1.взвешиваем(1) 1-ю и 2-ю
2. если вес равный убираем эти монеты и дальше работаем с кучкой 3
Иначе, с более легкой из них
3.делим оставшиеся четыре монеты на 2 кучки по 2 и взвешивем (2-раз)
4. выбираем более легкую, остается 2
монеты.
5. взвешиваем (3-раз) и определяем фальшивую.
:-)
======================================
Математическая головоломка месяца: август 2002 - решение
Какая из монеток фальшивая?
Несколько человек, среди которых Мигель Тенорио и Дейвид Стентон, решили
эту задачу при помощи четырех взвешиваний. На самом деле задача решается с помощью трех взвешиваний. Вот как это происходит:
Пронумеруем монеты: 1 2 3 4 5 6 7 8 9 10 11 12, и разделим их на три группы:
A [1 2 3 4]
B [5 6 7 8]
C [9 10 11 12]
1.
Взвесим монеты группы A и B. Если их вес окажется одинаковым, то мы узнаем, что фальшивая монета находится в группе C, а монеты в A и B - настоящие. Теперь давайте предположим, что это условие выполняется.
2. Возьмем три любые монеты из группы A или B (все они настоящие) и взвесим с
тремя монетами из C - к примеру, будем взвешивать монеты [1 2 3] и [9 10 11]. Здесь может быть два варианта:
a. Монеты имеют одинаковый вес - таким образом, монета номер 12 фальшивая, затем третье взвешивание этой монеты с любой другой определяет, тяжелее она или легче;
b. Монеты имеют разный вес, поэтому одна из монет, имеющих номер 9, 10 или 11 - фальшивка. (И если группа [9 10 11] легче, чем группа [1 2 3], то фальшивая монета легче, чем подлинная. Если группа [9 10 11] тяжелее, то вес фальшивки больший). В третьем взвешивании возьмем две монеты из
группы [9 10 11] и сравним их вес. Если их вес одинаков, то подделка - оставшаяся третья монета. Если нет, то Вы можете определить подделку, так как уже знаете, тяжелее или легче она по сравнению с другими монетами.
Теперь давайте вернемся первому шагу и рассмотрим другой - более сложный
вариант хода событий.
1. Мы сравнили вес монет групп A и B, он оказался разным, поэтому фальшивка находится в группе A или группе B. Кроме этого, теперь мы знаем, что монеты в группе C - подлинные*;
2. Предположим, что монеты группы A [1 2 3 4] тяжелее монет группы B [5 6 7
8]. Разделим группу A таким образом, чтобы мы взвешивали монеты [1 2] и [3 4]. К ним добавим по одной монете из группы B - на левую чашу весов, и С - на правую. Таким образом мы сравниваем вес монет [1 2 5] и [3 4 12]. Мы знаем, что монета номер 12 настоящая. В этой ситуации возможно три варианта.
1. Монеты [1 2 5] тяжелее. Но мы знаем, что монеты с номерами 3,4 и 5 - настоящие, так как мы положили их на разные чаши весов, и баланс при этом не менялся: монеты 3 и 4 были переложены с левой чаши на правую, а номер 5 - с правой на левую. Таким образом, фальшивая
монета находится под номером 1 или 2. Теперь мы также знаем, что вес фальшивки больше. Последнее взвешивание монет 1 и 2 точно устанавливает подделку - более тяжелую монету.
2. Монеты [3 4 12] тяжелее. Это означает, что поддельная монета была перемещена. Вероятно, что подделка - номер 3
или 4, и вес монеты больше. Подделкой также может быть монета номер 5, тогда вес фальшивки меньше. Последнее взвешивание монет 3 и 4 дает точный ответ. Если вес этих монет оказывается одинаковым, то подделка - номер 5. Если нет, то значит вес фальшивки больше массы номеров 3 и 4.
3.
Монеты с номерами [1 2 5] и [3 4 12] уравновешиваются. Это означает, что фальшивки нет на чашах весов, поэтому она должна находиться сред трех оставшихся монет групп А и В, то есть номеров [6 7 8]. Но мы знаем, что вес подделки меньше, так как при первом взвешивании номера [1 2 3 4] были тяжелее
группы [5 6 7 8]. Третье взвешивание, в котором на чаши весов кладется по одной монете, определяет подделку. Если мы сравним вес номеров 6 и 7, и он окажется одинаковым, то подделка - 8. В противном случае фальшивой является более легкая монета.
Более подробно решение задачи описано в
книге: Мачалевиц, Збинев и Фогель, Дэйвид Б, Как решать: современная эвристика, Спрингер, Берлин, Нью-Йорк, 2000 г. (ISBN: 3-540-66061-5)
======================================
Я как Шерлок Холмс - если расскажу откуда станет неинтересно :-)
Честно могу сказать что до самого сложного шага не додумался (как водится, за 10 минут :-) )
Мастер спорта, а что сообщение-то стер как задачку месяц решал? ;-) Мы-то все видели ;-)
Внимание! сейчас Вы не авторизованы и не можете подавать сообщения как зарегистрированный пользователь.
Чтобы авторизоваться, нажмите на эту ссылку (после авторизации вы вернетесь на
эту же страницу)
