Хорошая головоломка на выходные. Из девяти одинаковых с виду монет только одна настоящая. Из оставшихся восьми монет четыре весят одинаково между собой, но при этом они легче настоящей. Последние четыре монеты также весят одинаково между собой, но все они тяжелее настоящей. Как с помощью чашечных весов без гирь определить настоящую монету за шесть взвешиваний?
update
Ответ
Подробное решение по ссылке.
Мне сразу засчитаете?
ОтветитьУдалитьВот кстати, хотел поинтересоваться :)
УдалитьРассматриваются ли задачи на взвешивание, в которых нужно составить алгоритм, минимизирующий матожидание количества взвешиваний для нахождения фальшивой монеты?
:) Ссылку на ваше решение я в качестве ответа приготовил.
УдалитьЗадача хорошая, но я к сожалению уже на "Элементах" ее прочитал.
ОтветитьУдалитьА что если задать другое распределение легких и тяжелых монет?
Скажем, 3 фальшивых легких, 5 тяжелых?
2 и 6?
По идее, там легче будет настоящую найти. Как известно, в предельном случае (когда все фальшивые одного веса) достаточно двух взвешиваний.
И еще, можно ли доказать, что 6 - это необходимый минимум?
Или вот такой вариант задачи: неизвестно, сколько фальшивых монет тяжелых, а сколько легких. :)
ОтветитьУдалитьСколько понадобится взвешиваний для нахождения настоящей монеты?
В таком варианте начать, наверное, можно тоже с четырех взвешиваний непересекающихся пар... Подумаю :)
У меня стойкое ощущение, что достаточно будет тех же 6 взвешиваний, и более того, алгоритм такой же, как для исходной задачи. :)
Удалить