Страница Алексея Яшунского

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

Рассматривалась задача о поиске фальшивых монет среди настоящих. Достаточно известна следующая задача: пусть имеется 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 фальшивых монет эквивалентны. 😉