Есть классическая задача: Имеется $%N $% монет. Известно, что 1 из них фальшивая (легче настоящей). Также имеются чашечные весы без гирь, которые вмещают любое количество монет на каждой стороне весов. С помощью них можно определить относительный вес монет левой чаши весов, относительно правой(<,>,=). Необходимо определить минимальное количество взвешиваний, с помощью которых можно однозначно определить фальшивую монету.

Для любого N ответом на задачу будет $%\left\lceil \log _{ 3 }{ N } \right\rceil$%.

Интерес представляет общий случай, когда количество фальшивых монет равно $%M (M<=N) $% Здесь, например, дается верхняя оценка количества взвешиваний для 1, 2, 3, 4 фальшивых монет.

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

задан 8 Май '12 16:53

изменен 8 Май '12 20:56

%D0%A5%D1%8D%D1%88%D0%9A%D0%BE%D0%B4's gravatar image


5525

10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×770
×282

задан
8 Май '12 16:53

показан
1029 раз

обновлен
8 Май '12 20:56

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru