пятница, 8 августа 2014 г.

1 из 9

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

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

  1. Ответы
    1. Вот кстати, хотел поинтересоваться :)

      Рассматриваются ли задачи на взвешивание, в которых нужно составить алгоритм, минимизирующий матожидание количества взвешиваний для нахождения фальшивой монеты?

      Удалить
    2. :) Ссылку на ваше решение я в качестве ответа приготовил.

      Удалить
  2. Задача хорошая, но я к сожалению уже на "Элементах" ее прочитал.

    А что если задать другое распределение легких и тяжелых монет?
    Скажем, 3 фальшивых легких, 5 тяжелых?
    2 и 6?

    По идее, там легче будет настоящую найти. Как известно, в предельном случае (когда все фальшивые одного веса) достаточно двух взвешиваний.

    И еще, можно ли доказать, что 6 - это необходимый минимум?

    ОтветитьУдалить
  3. Или вот такой вариант задачи: неизвестно, сколько фальшивых монет тяжелых, а сколько легких. :)
    Сколько понадобится взвешиваний для нахождения настоящей монеты?

    В таком варианте начать, наверное, можно тоже с четырех взвешиваний непересекающихся пар... Подумаю :)

    ОтветитьУдалить
    Ответы
    1. У меня стойкое ощущение, что достаточно будет тех же 6 взвешиваний, и более того, алгоритм такой же, как для исходной задачи. :)

      Удалить