О выявлении фальшивых монет (к шестому заседанию математического кружка)

Математика Оставить комментарий

В силу причин личного характера протокол шестого заседания я никак не мог собраться написать и, в итоге, дотянул до последнего. Однако, до вечера ещё немного времени осталось, поэтому я попробую всё-таки что-то изобразить.

Рассматривалась задача о поиске фальшивых монет среди настоящих. Достаточно известна следующая задача: пусть имеется 9 монет, одинаковых внешне, одна из которых тяжелее других (фальшивая). Требуется за 2 взвешивания найти эту монету.

Решение этой задачи также достаточно известно, поэтому разбирались обобщения этой задачи, среди которых
а) Сколько взвешиваний надо, чтобы найти тяжелую монету среди n монет?
б) Сколько взвешиваний надо, чтобы найти 2 тяжелые монеты среди n монет?


Прежде всего замечу, что здесь пойдёт речь о доказательствах верхних оценок. Нижнюю оценку я придумал только что, во вторник она не обсуждалась.

Итак, для нахождения одной монеты из 9 действительно достаточно 2 взвешивания: взвесим 3 и 3 монеты. Возможные варианты:


OOO < OOQ
OOQ > OOO
OOO = OOO

В первом случае фальшивая монета (Q) в правой чаше весов, во втором случае - в левой чаше, а в третьем - среди тех трех монет, которые мы не взвешивали. В любом случае, получаем тройку монет, из которых надо выбрать одну более тяжёлую. Сравним две монеты из этих трёх; возможные варианты:

O < Q; Q > O; O = O

В каждом из случаев фальшивая монета определяется однозначно.

Этот метод обобщается на произвольное количество монет - n. Пусть l таково, что 3^l<n<=3^{l+1}.
Разделим монеты на три группы: 3^l, 3^l и всё, что осталось. Взвесим первые две. Если они равны по весу, то фальшивая монета в третьей. Если одна перевесила, то в ней. Далее применим тот же алгоритм к выбранной группе. Такая последовательность действий позволяет определить более тяжёлую монету за ]log_3 n[ (верхняя целая часть от логарифма n по основанию 3) действий.

Перейдём теперь к задаче нахождения двух тяжёлых монет. Пусть монет n, и l таково, что 3^l<n<=3^{l+1}. Выберем из монет две группы по 3^l монет в каждой и сравним их.

  • Если какая-то оказалась легче, то в ней заведомо не может быть фальшивых монет. Тогда в двух оставшихся группах либо в каждой по фальшивой монете, либо в одной группе две монеты (причём в той группе, которая перевесила в первом взвешивании, точно фальшивая монета есть). Из лёгкой группы (в которой все монеты настоящие) добавим монет в ту группу, которая ещё не взвешивалась, чтобы в ней стало 3^l монет. Теперь её можно сравнить с той группой, которая была более тяжёлой. Если они равны, то в каждой по тяжёлой монете. Если тяжёлая перевесила, значит обе фальшивые монеты в ней.
  • Если группы при первом взвешивании оказались равны, то они либо обе не содержат фальшивых монет, либо в каждой из них по фальшивой монете. Возьмём монеты одной из этих групп и добавим в ту, которая не взвешивалась, чтобы их там стало 3^l.

    Теперь сравним дополненную группу с той, которая участвовала во взвешивании. Возможны варианты:
    1. Они равны. Тогда в каждой из них по фальшивой монете (иначе получилось бы, что фальшивых монет нет вовсе). Более того, фальшивая монета находится среди тех, которые мы добавили в третью группу.
    2. Дополненная перевесила. Тогда в другой группе нет фальшивых монет, а значит их вообще не было в группах из первого взвешивания. Значит обе монеты в дополненной группе.
    3. Дополненная оказалась легче - невозможно.

Итак, мы потратили 2 взвешивания и пришли к такой ситуации. Для того, чтобы закончить решение нам потребуется либо найти 2 фальшивые монеты среди 3^l, либо два раза найти фальшивую монету среди 3^l. Несложно видеть, что за 2]log_3 n[ взвешиваний 2 тяжёлые монеты находятся.

Вопрос о поиске трёх тяжёлых монет пока открыт. Хотя, нижняя оценка, которую я придумал считается и для такого случая.

Кстати, задачи поиска k фальшивых монет и n-k фальшивых монет эквивалентны. 😉

2 комментария к “О выявлении фальшивых монет (к шестому заседанию математического кружка)”

  • Anonymous:

    нижняя оценка

    Любопытно было бы узнать придуманную нижнюю оценку для числа взвешиваний.
    Кстати, из каким соображений используется именно 3, а не 5 или 7 к примеру?
    В случае k монет из n тоже будет использоваться 3?

    • Re: нижняя оценка

      Словосочетание "используется 3" я, наверное, не совсем понимаю. Число 3 возникает прежде всего в связи с тем, что у одного взвешивания три (3) возможных исхода: перевесила одна чаша, перевесила другая, оказались равны.

      Нижняя оценка получается вот из каких соображений: у каждого взвешивания 3 исхода. У q взвешиваний различных исходов 3^q. Если, например, мы хотим найти k монет среди n мы должны уметь различать с помощью взвешиваний C_n^k различных ситуаций. Следовательно 3^q >= C_n^k, откуда q >= ]log_3 C_n^k[.

Оставить комментарий

Тема WordPress и иконки разработаны N.Design Studio
© 2019 Страница Алексея Яшунского RSS записей RSS комментариев Войти