update
Первый - Dendr. Ответ в комментариях.Из этой же серии - одна настоящая монета.
среда, 29 октября 2014 г.
12 монет
Из этой же серии - одна настоящая монета.
Подписаться на:
Комментарии к сообщению (Atom)
Из этой же серии - одна настоящая монета.
А в чем подвох? :) Это же классическая задача :)
ОтветитьУдалитьПросто обнаружил, что её ещё не было. Может кто-нибудь не знает. И в классической по-моему известно легче она или тяжелее, а здесь нет.
УдалитьМожно усложнить задачу.
ОтветитьУдалитьПусть монет не 12, а 14, из них одна эталонная (т.е. заведомо не фальшивая), а из остальных не более одной фальшивой (т.е. может и не быть), относительный вес которой неизвестен. Требуется с помощью трех взвешиваний определить, какая из монет фальшивая (и есть ли она вообще), и является ли она более легкой или более тяжелой по отношению к настоящей.
Наоборот, задача упростилась, как мне кажется. Ведь теперь 26 возможных вариантов из 27 исходов, то есть первое взвешивание должно разбить эти варианты на группы 9-9-8, затем "девятки" разбиваются единственным образом на 3-3-3, а "восьмерка" на 3-3-2. Ну и последнее взвешивание из трех (или двух) выделяет один.
ОтветитьУдалитьТам как раз 27 вариантов, включая ситуацию, когда фальшивой монеты нет. :)
УдалитьКонечно, разбивать нужно на равные части. Но чем это проще исходной формулировки задачи, все равно не понимаю :)
Возможно, из-за того, что сначала я решал первую, а потом, на опыте, вторую, так получилось. Действительно, такую задачу не помню (или забыл)
ОтветитьУдалитьПосле сделанного комментария чуть выше, поправил собственное решение (оно было больше эмпирическим), и раз никто не пытался, приведу его. А то вдруг кто-нибудь заглянет сюда, а ответа-то и нет. Решу при этом задачу из топика, а не дополнительную.
ОтветитьУдалитьИтак. Есть 12 возможностей, какая из монет фальшивая, и 2 варианта ее разновидности. Всего 24. За три взвешивания мы получим 27 исходов, что позволяет найти монету "с запасом". Понятно, что после 1-го взвешивания должно остаться не более 9 вариантов.
Пусть на 1-м взвешивании мы кладем на каждую чашу по N монет. Если перевесит левая чаша, то либо какая-то из левых монет тяжелая, либо какая-то из правых - легкая. Это 2N вариантов. Те же 2N при перевешивании правой. При равенстве, значит, 24-4N.
Теперь составим два неравенства:
2N<=9; 24-4N<=9
Только одно целое N удовлетворяет им, и это 4.
Таким образом, на первом взвешивании надо сравнивать 4 монеты с 4 другими. Тогда останется 8 вариантов по результатам взвешивания, которые вторым надо разбить на группы не более 3. Априорно на неравенства надо оставлять 3, на равенство - 2. (3+3+2=8)
Допустим, было неравенство. Монеты на перевесившей чашке помечу "Т", на другой - "Л", их всех по 4, и ровно одна фальшивая, то есть действительно тяжелая или легкая.
Перераспределим монеты на чашах так: ТТЛ -- ТТЛ, а ЛЛ отложим в сторону.
При равенстве фальшивка среди последней пары. Просто сравним одну из них с настоящей и так выделим фальшивку.
При неравенстве фальшивка либо среди Т-монет на перевесившей чашке, либо это Л-монета на противоположной. Остальные монеты настоящие, и пометки с них снимаем. В итоге останутся три монеты ТТЛ. Одним взвешиванием надо выявить фальшивку. Понятно, что удобнее всего взять пару ТЛ и сравнить ее с парой заведомо настоящих. Равенство - фальшивка последняя монета из этой тройки, неравенство - в зависимости от того, тяжелее или легче пара, фальшивка будет тяжелой или легкой из них двух (а какая из них какая - мы уже выяснили еще на 1-м этапе)
Допустим теперь, что на 1-м взвешивании было равенство. Значит, фальшивка среди 4 невзвешенных, обозначу их A B C D. Тут вариантов тоже несколько, мне нравится такой: взвешивание 2: сравниваем A и B, взвешивание 3: сравниваем A и C. И дальше смотрим табличку (равновесие "=", неравновесие "%")
== D
=% C
%=B
%%A
Все правильно, и объяснение хорошее.
УдалитьПравда, в последнем варианте есть шанс, что не удастся определить, является ли фальшивая монета тяжелой или легкой (если это D). C одной стороны, в условии это не требуется, но с другой, это легко исправить. :)
Спасибо, сам не мог (хотя, и не особо старался).
УдалитьДа, согласен с Ильёй. Предлагаю такой вариант при равенстве в 1 взвешивании:
Взвешиваем A, B, C и 3 настоящих.
Если равновесие, то D фальшивая и следующим взвешиванием определяем, легче она или тяжелее.
Если нет равновесия и A+B+C тяжелее (2 вариант - легче), то сравниваем A и B. Если равновесие, то фальшивая C и она тяжелее (легче). Если нет равновесия, то какая тяжелее (легче), та и фальшивая.