четверг, 11 апреля 2013 г.

Взвешивание на двух весах

Преамбула 

Возможно, вы слыхали о том, что такое puzzlesport. То бишь "чемпионаты по решению головоломок". В рамках этого вида спорта бывают и совсем диковинные звери - заочные соревнования, в которых некоторое небольшое число задач решается в течение многих недель и даже месяцев, причем допускаются и приветствуются командные решения. Вот именно таким соревнованием является ежегодный традиционный матч между Россией и Украиной, посвящённый памяти Андрея Ходулёва.

Так уж сложилось, что от России почти каждый год бывает какая-нибудь "монетная" задачка, и чаще всего - сделанная с моим участием. В силу специфики матча мы даем на него порой очень сложные сюжеты. Однако в прошлом году ничего интересного из сложных сюжетов я не придумал, и предложил банальную вариацию классики - одновременное взвешивание на нескольких весах. То есть "параллельные вычисления".

Вот условие матчевой задачи

У нас есть N внешне неразличимых монет (из которых одна фальшивая, неизвестно, легче или тяжелее остальных, все настоящие монеты весят одинаково) и ДВОЕ рычажных весов, взвешивания на которых мы можем делать параллельно. Каждое такое параллельное взвешивание на двух весах длится одну минуту. Для какого наибольшего числа монет N удастся отыскать фальшивую за 5 минут (время на перекладку монет для следующего взвешивания считаем пренебрежимо малым)?

Согласитесь, вариация очень естественная (лично для меня было удивительно то, что она новая).
Ниже - авторское решение.

Ответ: для 1561 монеты. [Комментарий: (5^5-3)/2.]

Алгоритм взвешиваний.

Будем описывать взвешивания в нотации A-B-C-D-E, где A и B - количества монет, которые в нём кладутся на чаши первых весов, C и D - количества монет на чашах вторых весов, а E - количество ПОДОЗРИТЕЛЬНЫХ монет, которые в этом взвешивании отложены и участия не принимают.
После каждого взвешивания мы будем отслеживать, сколько осталось подозрительных монет и каковы они. Типов подозрительных монет может быть всего три: ФЛ "может оказаться фальшивой лёгкой", ФТ "может оказаться фальшивой тяжёлой" и ФЛТ "может оказаться фальшивой, как лёгкой, так и тяжёлой". До первого взвешивания все монеты отнесены к типу ФЛТ.

1 минута. 312-312-312-312-313.
Результатов взвешиваний может быть пять (<=, >=, =<, =>, ==), но принципиальных случаев два -
А. Каждые весы остались в равновесии.
  Наш вывод: все монеты на весах настоящие (это даёт нам большой запас настоящих монет, который пригодится в следующих взвешиваниях), 313 монет остались типом ФЛТ.
Б. На каких-то весах неравенство.
  Наш вывод: все монеты других весов и все 313 отложенных монет - настоящие (см. выше
комментарий о запасе); 312 монет с более лёгкой чаши отнесены к типу ФЛ, 312 монет с более тяжёлой чаши отнесены к типу ФТ.

Итого после первой минуты мы свели задачу либо к "предыдущей" (для 4 минут и 313 монет, при этом у нас есть запас настоящих монет, назовём это подзадачей А4), либо к такой: "имеется 312 монет типа ФЛ и 312 монет типа ФТ, найти фальшивую за 4 минуты" (назовём её подзадачей Б4).

А4: имеется 313 монет ФЛТ и запас настоящих, надо найти фальшивую за 4 минуты
Б4: имеется 312 монет ФЛ, 312 монет ФТ и запас настоящих, найти фальшивую за 4 минуты.

Дальнейшая схема такова - за очередную минуту сводим подзадачу А_n либо к А_{n-1}, либо к Б_{n-1} в зависимости от результата взвешиваний, а подзадачу Б_n - всегда к Б_{n-1}.

А3: имеется 63 монеты ФЛТ и запас настоящих, найти фальшивую за 3 минуты
А2: имеется 13 монет ФЛТ и запас настоящих, найти фальшивую за 2 минуты
А1: имеется 3 монеты ФЛТ и запас настоящих, найти фальшивую за 1 минуту

Б3: имеется 63 (62) монеты ФЛ и 62 (63) монеты ФТ, найти фальшивую за 3 минуты
Б2: имеется 13 (12) монеты ФЛ и 12 (13) монеты ФТ, найти фальшивую за 2 минуты
Б1: имеется  3 ( 2) монеты ФЛ и  2 ( 3) монеты ФТ, найти фальшивую за 1 минуту

Дальше мы разберёмся с решениями всех этих задач "от простых к сложным".

Решение задачи А1 тривиально: 1-(0+1Н)-1-(0+1Н)-1здесь "0+1Н" означает, что на чашу кладётся одна заведомо настоящая монета. Если весы покажут равновесие, то фальшивой является отложенная монета.

Решение задачи Б1 тоже совсем просто: (1ФЛ+1ФТ)-(0+2Н)-(1ФЛ+1ФТ)-(0+2Н)-1здесь "1ФЛ+1ФТ" означает, что на чашу кладутся две монеты - одна ФЛ и одна ФТ. На другую чашу кладутся две настоящих. Если весы покажут равновесие, то фальшивой является отложенная монета - она может быть как ФЛ, так и ФТ. Если же одни весы покажут неравенство, то по его знаку мы сразу определим, какая из подозрительных монет действительно фальшивая.

Сведение задачи Б2 к Б1: (3ФЛ+2ФТ)-(3ФЛ+2ФТ)-(2ФЛ+3ФТ)-(2ФЛ+3ФТ)-5.
Отложенные монеты могут быть либо 3ФЛ и 2ФТ, либо 3ФТ и 2ФЛ. Если какие-то весы покажут неравенство, то подозрительными остаются ФТ-монеты с более тяжёлой чаши и ФЛ-монеты с более лёгкой. В любом исходе получается набор монет, удовлетворяющий условию Б1.
Аналогично сводится Б3 к Б2 и Б4 к Б3.

Сведение задачи А2 к А1 или Б1: (2+1Н)-3-(2+1Н)-3-3Здесь "2+1Н" - это две ФЛТ-монеты и одна настоящая. После равновесия получаем А1, а после неравновесия - Б1.
Аналогично сводится А3 к А2 и А4 к А3.


Комментариев нет:

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