?

Log in

No account? Create an account

Взвешивание монет (задача Саладина) - Clittary Hilton

Jan. 27th, 2010

02:07 pm - Взвешивание монет (задача Саладина)

Previous Entry Share Next Entry

Юзер 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).

Comments:

[User Picture]
From:maxnicol
Date:January 28th, 2010 05:18 am (UTC)
(Link)
рыцаря-то отпустили? ))
(Reply) (Thread)
[User Picture]
From:clittary_hilton
Date:January 28th, 2010 08:10 pm (UTC)
(Link)
опустили рыцаря... (сокрушённо) азиатчина-с !
(Reply) (Parent) (Thread) (Expand)
From:kadiyabdurahman
Date:January 28th, 2010 07:23 am (UTC)

Это стоит лимерика!

(Link)
(Перенес из той ветки)

Угодил бедный рыцарь в темницу
Но пришла темной ночью девица
Что-то долго считала
Чем-то тихо шуршала
И бросала шпаргалку в темницу!

(вариант № 2)

Угодил бедный рыцарь в темницу
Но явилась лихая девица
Увезла при луне
На прекрасном коне
И теперь он обязан жениться!
(Reply) (Thread)
[User Picture]
From:clittary_hilton
Date:January 28th, 2010 08:13 pm (UTC)

Re: Это стоит лимерика!

(Link)
В Лабиринте сегодня нарядно.
Мусор всякий и нить Ариадны
Смели в уголок.
Блестит потолок...
Минотавр напился изрядно.
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:fedred
Date:February 9th, 2010 06:57 pm (UTC)

отлично изложено

(Link)
Среди многочисленных задач на взвешивание эта задача уникальна. Составить аналогичную задачу с другим числом монет/взвешиваний очень трудно, ибо здесь вся хитрость (и сложность) вытекают из близости чисел 24 (точнее 25) и 27.
(Reply) (Thread)
[User Picture]
From:clittary_hilton
Date:February 9th, 2010 07:21 pm (UTC)

Re: отлично изложено

(Link)
Спасибо, я согласна с тем, откуда вытекают хитрость и сложность, но с основным вашим утверждением согласиться не могу. Чем вас не устраивает "обобщенная" задача Саладина с 40 монетами и 4-мя взвешиваниями?

С учетом возможности отсутствия фальшивой монеты имеется ровно 81 конфигурация и ровно 34 возможных результатов измерения. Простейшая процедура описанная выше продолжает работать, и построить 4 измерения нетрудно, добавив к XYZ еще одну букву...

С точки зрения отсутствия избыточной информации, задача 40:4 элегантнее, нежели 12:3... Саладину было, видимо, просто жаль молодого рыцаря!

(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:sascha_tiptop
Date:February 11th, 2010 12:52 pm (UTC)
(Link)
а как быть, если нельзя надписать или как-то обозначить монеты,
а только перевернуть (орёл или решка) или сложить в какую-либо
геометрическую фигуру.
(Reply) (Thread)
[User Picture]
From:clittary_hilton
Date:February 11th, 2010 04:35 pm (UTC)
(Link)
если монеты фундаментально неразличимы, над еще разобраться, фермионы это или бозоны...
(Reply) (Parent) (Thread)
From:kadiyabdurahman
Date:February 17th, 2010 11:55 am (UTC)
(Link)
Меня мучает еще одна задача. Я прочитал, что букашка не может убежать от Ахиллеса и мне стало за нее обидно. Я решил изменить условия и вот что получилось:
Ахиллес и букашка стартуют из одной точки практически одновременно, но Ахиллес на малую величину раньше. Бежит он, разумеется, быстрее (с постоянной скоростью V). Но справедливости ради для букашки есть две поблажки. Ахиллес держит один конец эластичной ленты, другой ее конец привязан к точке старта. Букашка ползет также с постоянной скоростью по ленте. Догонит ли букашка Ахиллеса? При каких граничных условиях?
(Reply) (Thread)
[User Picture]
From:clittary_hilton
Date:February 17th, 2010 04:16 pm (UTC)
(Link)
В каком смысле букашка ползет также с постоянной скоростью по ленте? Если скорость постоянна по отношению к точке старта, то букашке ничего не поможет...

С другой стороны, представим себе букашку, ползущую по экватору с постоянной угловой скоростью ω. А земля расширяется, так что длина экватора растет со скоростью V. Конечно, какова бы ни была V, букашка совершит кругосветное путешествие за время 2π/ω... однако, при достаточно большой V, скорость букашки по касательной может превысить скорость света (что нисколько не противоречит специальной теории относительности).

Ваша задача как-то обыгрывает старинный вопрос в общей теории относительности: в замкнутой вселенной путешественник улетевший с постоянной скоростью всегда ли вернется с обратной стороны?

Edited at 2010-02-17 04:31 pm (UTC)
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:nu57
Date:February 27th, 2010 06:47 am (UTC)
(Link)
Спасибо, решила, перепостила.
(Reply) (Thread)
[User Picture]
From:clittary_hilton
Date:February 27th, 2010 05:46 pm (UTC)
(Link)
обратите внимание на комментарии юзера fedred о возможности обобщения задачи (см. выше)... для меня это оказалось сюрпризом, уже после того как я решила задачу, казалось бы, досконально!
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:dotsog
Date:March 3rd, 2010 10:24 pm (UTC)

Это не усложнение:)

(Link)
настоящее усложнение это:
пусть есть m - монет и q - взвешиваний
1)вопрос каковы шансы рыцаря при использовании оптимальной стратегии
2)пример оптимальной стратегии
или другая идея(попроще):
сделать недостаточное количество взвешиваний - но разрешить один раз воспользоваться подсказкой Джина
(чем может помочь Джин - по вкусу: устанавливать фальшивость одной монеты, определять наличие фальшивой монеты в группе...)
в общем, есть чем поглумиться над участниками олимпиад
(Reply) (Thread)
[User Picture]
From:clittary_hilton
Date:March 4th, 2010 03:10 am (UTC)

Re: Это не усложнение:)

(Link)
Ваша правда...
(Reply) (Parent) (Thread)
[User Picture]
From:8aetherous8
Date:March 9th, 2010 02:57 pm (UTC)

Кстати, в литературе присутствует

(Link)
Пирс Энтони, "С запутанным клубком"

Там другой сюжет, но головоломка та же :)
(Reply) (Thread)
[User Picture]
From:clittary_hilton
Date:March 9th, 2010 04:00 pm (UTC)

Re: Кстати, в литературе присутствует

(Link)
не читала... does the skein disentangle ultimately ?
(Reply) (Parent) (Thread)