Решение теоретико-информационное. Весы и 12 монет (#102)
Для начала немного теории.
Общая постановка. Пусть в известном нам конечном множестве из N элементов загадали один элемент, который нам нужно найти. Мы можем делать запросы определённого типа и получать ответ из k вариантов (например, в случае ответов типа «да/нет» k = 2). Каково минимальное необходимое количество запросов для гарантированного определения элемента?
После каждой операции в лучшем случае количество претендентов сокращается в k раз, поэтому после n запросов мы будем иметь в лучшем случае N / kⁿ претендентов. Для однозначного ответа необходимо, чтобы это количество было не более 1, поэтому количество запросов n ≥ logₖN.
Решение задачи. В изначальном решении нами никак не обосновывался выбор количества монет в 1-м взвешивании. Как будто это было сделано наугад или простым перебором. Сейчас же мы строго покажем, что это единственный вариант, доставляющий решение задачи.
Понятно, что имеет смысл класть на чаши только равное количество монет.
Априори имеем N = 12 x 2 = 24 варианта для фальшивки. Каждое взвешивание имеет три возможных результата (<, >, =), то есть k = 3. Поэтому n ≥ log₃24 или n ≥ 3. Следовательно, в условии задачи не требуют невозможного, и есть смысл продолжать.
1-е взвешивание. Кладём на чаши по x монет.
Если =, то фальшивка среди оставшихся 12–2x монет. То есть на оставшиеся два взвешивания приходится 2(12–2x) исходов или в соответствии с формулой выше 2 ≥ log₃2(12–2x) или 9 ≥ 24–4x или x ≥ 3.75.
Если <>, то фальшивка среди 2x монет на чашах. То есть на оставшиеся два взвешивания приходится 2x исходов (так как относительный вес для каждого претендента уже определён) или в соответствии с формулой выше 2 ≥ log₃2x или 9 ≥ 2x или x ≤ 4.5.
Таким образом, для первого взвешивания однозначно x = 4. Другими словами, нужно обязательно класть на чаши по 4 монеты.
2-е взвешивание, если в 1-м =. Тогда фальшивка среди оставшихся четырёх монет. Положим на чаши x и y монет из этих претендентов. Для уравнивания количества монет на двух чашах будем использовать настоящие монеты, которые заведомо будут обнаружены после 1-го взвешивания. Проведём аналогичные рассуждения.
Если =, то фальшивка среди оставшихся 4–(x + y) монет. У нас осталось одно взвешивание, поэтому 1 ≥ log₃2(4–(x + y)) или 3 ≥ 8–2(x + y) или x + y ≥ 2.5.
Если <>, то фальшивка среди (x + y) монет на чашах, то есть 1 ≥ log₃(x + y) или x + y ≤ 3.
Таким образом, во 2-м взвешивании должно участвовать ровно 3 подозрительных монеты. Вернёмся к возможным результатам:
Если =, то фальшивка — это оставшаяся монета из четырёх претендентов. За последнее взвешивание определяем её относительный вес.
Если <>, то фальшивка среди 3 подозрительных монет на чашах. Если во 2-м взвешивании все три подозрительных лежали на одной чаше (x = 3, y = 0), то это взвешивание показало относительный вес. Последним взвешиванием сравниваем две любые подозрительные и, зная относительный вес, легко определяем фальшивку. Можно решить и другим способом, если x = 2, y = 1.
2-е взвешивание, если в 1-м <>. Пусть без ограничения общности левая чаша при 1-м взвешивании легче. То есть фальшивка среди 8 монет на этих чашах. Тогда при 2-м взвешивании положим на левую чашу a монет с левой чаши 1-го взвешивания и b монет с правой чаши 1-го взвешивания. А на правую чашу — соответственно c и d монет с левой и правой чаши 1-го взвешивания.
Пусть s := a + b + c + d ≤ 8.
Если =, то фальшивка среди оставшихся 8 — s монет, то есть 1 ≥ log₃(8–s) или s ≥ 5.
Если <, то фальшивка среди s монет, причём, если она среди монет a или d, то a + d ≤ 3. Аналогично, b + c ≤ 3.
У данной системы неравенств несколько решений и можно проверить, что любое из них даст решение задачи. Например, a = b = 2, c = d = 1. Дальнейший алгоритм достроить несложно и оставляется читателю.
