January 5th, 2008

lenin

Сложная задача с интуитивно неочевидным ответом

Имеется N монет, среди которых есть одна фальшивая, чуть легче настоящих, и электронные весы с разрешением в 0.1 г. Настоящие монеты весят целое число граммов, а фальшивая - на 0.05 г легче, так что определить, что во взвешиваемых монетах есть фальшивая, удается с вероятностью 50% (если все монеты настоящие, весы стопроцентно показывают целое число). Монет можно взвешивать любое число зараз.

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