Взвешивание монет (задача Саладина)
Юзер kadiyabdurahman задал мне головоломку на взвешивание монет, под названием " Задача Саладина". Хотя за свою долгую жизнь я нарешалась задач на взвешивание, этой задачи мне не встречалось и пришлось поломать голову. Задача довольно занятная, особенно тем, что допускает на первый взгляд нетривиальное усложнение.
История: Эта история случилась давным-давно, еще во времена крестовых походов. Один из рыцарей был захвачен мусульманами в плен и предстал перед их предводителем - султаном Саладином, который объявил, что освободит пленника и его коня, если получит выкуп в 100 тысяч золотых монет.
- О, великий Саладин, - обратился тогда к султану рыцарь, у которого за душой не было ни гроша, - ты меня лишаешь последней надежды. У нас на родине мудрому и находчивому пленнику дается шанс выйти на свободу. Если он решит заданную головоломку, его отпускают на все четыре стороны, если нет - сумма выкупа удваивается!
- Да будет так, - ответил Саладин, и сам обожавший головоломки. - Слушай же. Hе справишься с задачей до утра - пеняй на себя!
Задача Саладина: Тебе дадут двенадцать золотых монет и простые весы с двумя чашками, но без гирь. Одна из монет фальшивая, однако неизвестно, легче она или тяжелее настоящих. Ты должен найти ее всего за три взвешивания.
Усложнение: Ты должен не только найти фальшивую монету, но и указать, легче или тяжелее она остальных. Более того, фальшивой монеты может и не быть вовсе и, если так, ты тоже обязан это указать!
Решение:
Перенумеруем 12 монет: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12;
Перенумеруем 24 конфигурации (возможные "состояния" системы, как сказали бы физики), 1L, 2L, ..., 12L, 1H, 2H, ..., 12H, где, например, 7H означает конфигурацию, где 7-я монета тяжелая;
Перенумеруем чашки: левая (Л), правая (П) и отдыхающая (О);
Перенумеруем результаты измерения, XYZ, где каждый символ может принимать три значения, Л (левая чашка перевесила), П (правая чашка перевесила), О (равновесие, то есть возможный виновник в отдыхающей чашке). Например, XYZ = ЛПО означает результат, в котором в 1-ом измерении перевесила левая чашка, во 2-ом правая, а в 3-ем восторжествовало равновесие. На первый взгляд, всего может быть 33 = 27 вариантов результатa, но некоторые (три) из них реализоваться не могут, ибо всего есть лишь 24 конфигурации. Таким образом, правильно выбранные измерения содержат излишнюю информацию, которую можно использовать для "усложнения" задачи. Саладин мог оставить возможность отсутствия фальшивой монеты, добавив тем самым 25-ю конфигурацию "N" (все монеты нормальные).
Выберем три взвешивания, располагая по четыре монеты в каждой из трех чашек, так чтобы каждая конфигурация приводила к однозначному результату. Регулярная простейшая процедура выбора описана в конце нашего повествования. Эмпирически, достаточно потребовать, чтобы никакие две монеты не "спаривались" во всех трех измерениях (то есть, не лежали на той же чашке или на противоположных неотдыхающих чашках). Иными словами, монеты могут спариваться, но не всегда, а максимум дважды. Например, выберем разбиение монет на группы для взвешивания так:
# Левая Правая Отдыхающая (1) 1,2,3,4 5,6,7,8 9,10,11,12 (2) 1,8,9,11 3,4,5,10 2,6,7,12 (3) 3,7,9,12 1,4,6,11 2,5,8,10
Каждая конфигурация приводит к однозначному результату XYZ. Например, конфигурация 1L (1-я монета легкая) даёт ЛЛП, причем никакaя другая конфигурация к ЛЛП не приводит (ЛЛП означает, что в 1-ом и 2-ом измерениях перетянула чашка Л, а в 3-ем - чашка П). Конфигурация 2L (2-я монета легкая) дает ЛОО (что означает, что в 1-ом измерении перетянула чашка Л, а во 2-ом и 3-ем осуществилось равновесие.
Обратим внимание, что никакая конфигурация не приведет к ЛЛЛ, ППП, или ООО. Если бы Саладин усложнил задачу, добавив 25-ю конфигурацию "N" (все монеты нормальные), то очевидно результат ООО мог бы осуществиться (N↔ООО).
Перечислим все конфигурации и соответствующие им результаты измерений в виде таблицы:
1L → ЛЛП 1H → ППЛ 2L → ЛОО 2H → ПОО 3L → ЛПЛ 3H → ПЛП 4L → ЛПП 4H → ПЛЛ 5L → ППО 5H → ЛЛО 6L → ПОП 6H → ЛОЛ 7L → ПОЛ 7H → ЛОП 8L → ПЛО 8H → ЛПО 9L → ОЛЛ 9H → ОПП10L → ОПО 10H → ОЛО11L → ОЛП 11H → ОПЛ12L → ООЛ 12H → ООП
В силу однозначности таблицы направление стрелок можно перевернуть и тем самым избежать гнева Саладина. Естественно, решений (в смысле выбора разбиения монет для взвешивания) имеется множество и вариант представленный выше лишь один из возможных. Найти разбиение, которое работает, нетрудно эмпирически, но можно следовать регулярной "процедуре"; простейшая процедура выбора начинается с желаемой таблицы результатов. Естественно, достаточно составить половину таблицы (соответствующую тому что фальшивая монета L) - вторая половина получится автоматически (заменой Л ↔ П).
Простейшая процедура:
Напишем колонку результатов из 12-ти XYZ, такую как 3-я колонка вышеприведенной таблицы. Все что надо потребовать, что никакой результат не повторялся дважды, а также чтобы колонка не содержала "противоположного" результата (то есть, если мы написали ОЛЛ, то результат ОПП должен быть исключен). Перенумеруем строки колонки (тем самым появляется 1-я колонка таблицы). После этого, разбиение монет на три измерения получается простым считыванием. Значение X определяет место (чашку) монеты в первом измерении, Y во втором, и Z в третьем. Так например, считывая средние буквы (Y) колонки, мы положим во втором измерении в левую чашку монеты (1,8,9,11), а в правую (3,4,5,10).