среда, 29 октября 2014 г.

12 монет

Из 12 одинаковых с виду монет одна фальшивая. Она отличается по весу, но неизвестно в какую сторону. То есть может быть как легче, так и тяжелее остальных. Как с помощью трёх взвешиваний на чашечных весах без гирь определить фальшивую монету?
update
Первый - Dendr. Ответ в комментариях.


Из этой же серии - одна настоящая монета.

9 комментариев:

  1. А в чем подвох? :) Это же классическая задача :)

    ОтветитьУдалить
    Ответы
    1. Просто обнаружил, что её ещё не было. Может кто-нибудь не знает. И в классической по-моему известно легче она или тяжелее, а здесь нет.

      Удалить
  2. Можно усложнить задачу.
    Пусть монет не 12, а 14, из них одна эталонная (т.е. заведомо не фальшивая), а из остальных не более одной фальшивой (т.е. может и не быть), относительный вес которой неизвестен. Требуется с помощью трех взвешиваний определить, какая из монет фальшивая (и есть ли она вообще), и является ли она более легкой или более тяжелой по отношению к настоящей.

    ОтветитьУдалить
  3. Наоборот, задача упростилась, как мне кажется. Ведь теперь 26 возможных вариантов из 27 исходов, то есть первое взвешивание должно разбить эти варианты на группы 9-9-8, затем "девятки" разбиваются единственным образом на 3-3-3, а "восьмерка" на 3-3-2. Ну и последнее взвешивание из трех (или двух) выделяет один.

    ОтветитьУдалить
    Ответы
    1. Там как раз 27 вариантов, включая ситуацию, когда фальшивой монеты нет. :)

      Конечно, разбивать нужно на равные части. Но чем это проще исходной формулировки задачи, все равно не понимаю :)

      Удалить
  4. Возможно, из-за того, что сначала я решал первую, а потом, на опыте, вторую, так получилось. Действительно, такую задачу не помню (или забыл)

    ОтветитьУдалить
  5. После сделанного комментария чуть выше, поправил собственное решение (оно было больше эмпирическим), и раз никто не пытался, приведу его. А то вдруг кто-нибудь заглянет сюда, а ответа-то и нет. Решу при этом задачу из топика, а не дополнительную.

    Итак. Есть 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

    ОтветитьУдалить
    Ответы
    1. Все правильно, и объяснение хорошее.
      Правда, в последнем варианте есть шанс, что не удастся определить, является ли фальшивая монета тяжелой или легкой (если это D). C одной стороны, в условии это не требуется, но с другой, это легко исправить. :)

      Удалить
    2. Спасибо, сам не мог (хотя, и не особо старался).
      Да, согласен с Ильёй. Предлагаю такой вариант при равенстве в 1 взвешивании:
      Взвешиваем A, B, C и 3 настоящих.
      Если равновесие, то D фальшивая и следующим взвешиванием определяем, легче она или тяжелее.
      Если нет равновесия и A+B+C тяжелее (2 вариант - легче), то сравниваем A и B. Если равновесие, то фальшивая C и она тяжелее (легче). Если нет равновесия, то какая тяжелее (легче), та и фальшивая.

      Удалить