Есть n монет, среди которых одна фальшивая - легче всех остальных. Также есть весы с двумя чашами, на которые за один раз можно класть любое количество монет. Докажите, что:

а) фальшивую монету можно найти за $$\log_{3}n +\operatorname O(1)$$ взвешиваний

б) для ее нахождения необходимо $$\log_{3}n + \Omega(1)$$ взвешиваний

задан 6 Фев '18 21:29

изменен 6 Фев '18 21:30

10|600 символов нужно символов осталось
1

б) Пусть мы можем определить фальшивую монету за k взвешиваний. Тогда при каждом взвешивании имеется три исхода. Протокол схемы взвешиваний состоит из k троичных символов. Таких протоколов 3^k. Если по заданному протоколу мы можем узнать, какая из монет фальшивая, то требуется различить n случаев (должна существовать сюръекция 3^k на n). Для этого необходимо 3^k>=n, то есть k>=log_3(n).

а) Делим монеты на три примерно равные части. А именно, если n=3m+1, то пусть части имеют мощность m+m+(m+1), а при n=3m+2 полагаем n=(m+1)+(m+1)+m. Тогда после одного взвешивания, независимо от исхода, мы получаем ту же задачу для числа монет, равного m или m+1, то есть количество уменьшается примерно втрое. Индукцией по n легко проверить, что если 3^{k-1} < n <=3^k, то k взвешиваний достаточно. То есть k не превосходит округлённого значения log_3(n) до ближайшего целого в сторону увеличения.

ссылка

отвечен 6 Фев '18 23:21

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×916

задан
6 Фев '18 21:29

показан
551 раз

обновлен
6 Фев '18 23:21

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

по почте:

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

по RSS:

Ответы

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

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