Загадка Салах ад-Дина

Давным-давно, во времена Крестовых походов, один из славных рыцарей папского воинства был захвачен в плен мусульманами. А поскольку роду он был знатного, то предстал перед судом, самого Салах ад-Дина, султана Египта и Сирии. Правитель могущественной империи, недолго думая, предложил рыцарю традиционный вариант: смерть или выкуп за сто тысяч золотых монет. У пленника же за душой не было и ломаного гроша. Поэтому он взмолился к султану: «О великий предводитель империи, в моей стране на родине есть обычай: пленнику задают загадку, если он угадает, его отпускают, если нет – сумма выкупа удваивается».

Салах ад-Дин, сам большой любитель головоломок, решил, что это неплохая идея. И предложил рыцарю такую задачку.

Тебе принесут дюжину золотых монет и простые весы с двумя чашами (без гирь). Одна из монеток фальшивая. То есть, ее вес отличается от остальных. Но неизвестно, тяжелее она или легче. Тебе необходимо определить фальшивку всего за три взвешивания. Время – до утра. Если не справишься, завтра твоя голова будет украшать ворота моего замка.

А справились бы вы на месте рыцаря?

Ответ:

У этой задачи может быть несколько решений. Вот одно из них.

Итак, делим все монеты на три кучки, пусть это будут А1А2А3А4, Б1Б2Б3Б4, В1В2В3В4. Взвешиваем две из них: А и Б. Тогда возможны два варианта:

Вес кучек одинаковый. В таком случае фальшивая монета однозначно в группе В.

Берем любые три монеты из оставшихся (А или Б), зная, что они точно настоящие. И сравниваем на весах В1В2В3 с любыми эталонными, например, А1А2А3 (это могут быт любые комбинации из трех монет групп А и Б).

Если кучки равновесны, то фальшивая монета В4, если неравновесны, то ненастоящая монета - одна из В1В2В3, причем теперь мы точно знаем, тяжелее она или легче.

В последнем взвешивании берем любые две монеты из В1В2В3 и сравниваем между собой. Если весы показывают, что монеты равны по весу, то фальшивая та, которая не взвешивалась. В противном случае поддельная монета - легче или тяжелее настоящей (мы уже узнали, в какую сторону отличается ее вес из предыдущего теста).

Вес кучек при самом первом взвешивании неодинаковый. Для нас важно заметить, какой набор тяжелее: А или Б. Предположим, что кучка А весит больше.

Во втором взвешивании покладём на чаши весов такие группы: А1В1В2В3 (понятно, что все монеты из группы В – настоящие) и Б1А2А3А4.

Если вес на чашах одинаков, то фальшивка среди оставшихся Б2Б3Б4. Кроме того, мы помним, что эта группа была легче. Другими словами, остается найти ту монету из трех, которая меньше по весу. Делается это третьим взвешиванием двух монет Б2 и Б3. Если весы покажут, что монеты равны по массе, то фальшивка – та, которую не взвешивали. Если нет, то та, которая легче.

Если же чаши весов покажут разный результат, причем та чаша, где больше монет из группы А, так и останется тяжелее, то фальшивка А1 или Б1. В третьем взвешивании любую из этих монет необходимо сравнить с эталонной. При наличии разницы - фальшивка лежит на весах, при ее отсутствии – нет.

Если чаши покажут разный результат, но неравенство изменилось, то есть группа, где больше монет А станет легче, то фальшивка среди них. Достаточно взвесить две любые монеты из тройки А2А3А4. При равном результате – фальшивка на столе, при неравном ненастоящая та, которая, в нашем случае, тяжелее.