Задача Саладина
Эта история случилась давным-давно, еще во времена крестовых походов. Один из рыцарей был захвачен мусульманами в плен и предстал перед их предводителем - султаном Саладином, который объявил, что освободит пленника и его коня, если получит выкуп в 100 тысяч золотых монет.
"О, великий Саладин, - обратился тогда к султану рыцарь, у которого за душой не было ни гроша, - ты лишаешь последней надежды.
У меня на родине мудрому и находчивому пленнику дается шанс выйти на свободу. Если он решит заданную головоломку, его отпускают на все четыре стороны, если нет - сумма выкупа удваивается!"
"Да будет так, - ответил Саладин, и сам обожавший головоломки. - Слушай же. Тебе дадут двенадцать золотых монет и простые весы с двумя чашками, но без гирь. Одна из монет фальшивая, однако неизвестно, легче она или тяжелее настоящих. Ты должен найти ее всего за три взвешивания. Не справишься с задачей до утра - пеняй на себя!" А вы смогли бы выкрутиться?
Ответ: Представим два решения: - Это одна из самых сложных головоломок с фальшивыми монетами. Напомним, что фальшивая монета может оказаться и легче, и тяжелее настоящих. Проверить это, а также выяснить, какая именно фальшивая, вам нужно всего за три взвешивания. Схема на рисунке показывает способ решения. Каждой монете присвоен номер, и они взвешиваются в разных комбинациях. Каждое взвешивание изображено в виде прямоугольников. В верхней части указаны монеты которые лежат на левой чашке весов, а в нижней части указаны монеты которые лежат на правой чашке весов. Буквы л, п, р обозначают какая чашка весов перевесила левая, правая или было равенство. В результате указан порядковый номер монеты и легкая она или тяжелая. Буквы нв говорят о неверности такого исхода.
2. ------- 3. | старт | 4. ------- 5. | 6. ------- 7. п|1,2,3,4|л 8. +---------------|5,6,7,8|--------------+ 9. | ------- | 10. ----- |р ----- 11. п|1,3,5|л | п|1,3,5|л 12. +--------|2,4,6|--------+ | +--------|2,4,6|--------+ 13. | ----- | | | ----- | 14. | |р | | | |р | 15. --- --- --- | --- --- --- 16.п| 1 |л п| 7 |л п| 2 |л | п| 2 |л п| 7 |л п| 1 |л 17.+-| 3 |-+ +-| 8 |-+ +-| 4 |-+ | +-| 4 |-+ +-| 8 |-+ +-| 3 |-+ 18.| --- | | --- | | --- | | | --- | | --- | | --- | 19.| |р | | |р | | |р | | | |р | | |р | | |р | 20.1л 6т 3л 8т нв 7т 2л 5т 4л | 4т 5л 2т 7л нв 8л 3т 6л 1т 21. | 22. ----- 23. п| 1,9 |л 24. +--------|10,11|--------+ 25. | ----- | 26. | |р | 27. --- --- --- 28. п| 10|л п| 11|л п| 10|л 29. +-| 11|-+ +-| 12|-+ +-| 11|-+ 30. | --- | | --- | | --- | 31. | |р | | |р | | |р | 32. 11т 9л 10т 12т нв 12л 10л 9л 11л - Вариант решения, которое нашёл Сумаруков Стас:
Эта задача была блестяще разобрана К. Л. Стонгом в майском номере журнала Scientific American за 1955 год. Одно из ее решений (а их довольно много) связано с троичной системой.
Сначала запишите все числа от 1 до 12 в троичной системе. Замените в каждом числе цифру 2 на 0, а 0 на 2 и запищите рядом результат. У вас получится три столбца чисел:
1 001 221
2 002 220
3 010 212
4 011 211
5 012 210
6 020 202
7 021 201
8 022 200
9 100 122
10 101 121
11 102 120
12 110 112
Внимательно изучив эти числа, вы обнаружите все числа, в которых встречаются сочетания 01, 12, 20. Каждой из двенадцати монет поставим в соответствие одно из этих чисел.
При первом взвешивании на левую чашу весов кладем четыре монеты, обозначенные числами, которые начинаются с 0, а на правую чашу весов кладем те четыре монеты, которым соответствуют числа, начинающиеся с 2. Если монеты уравновесят друг друга, вы можете утверждать, что число, которое отвечает фальшивой монете, начинается с 1. Если перевесит левая чашка, то искомое число начинается с 0, а если правая - то с 2.
Взвешивая монеты второй раз, их надо распределять в зависимости от средней цифры. Если в центре стоит 0, монета кладется на левую чашу, если 2 - на правую. Вторая цифра числа, обозначающего фальшивую монету, определяется точно так же, как определялась его первая цифра при первом взвешивании.
Производя последнее взвешивание, вы кладете налево те монеты, которые обозначены числами, оканчивающимися на 0, а монеты, соответствующие числам, имеющим на конце 2, вы кладете на правую чащу весов. Таким образом вы узнаете последнюю цифру нужного вам числа.
Hа рис. 223 (который я убрал) видно, что после трех взвешиваний фальшивой оказалась монета 201. Она явно тяжелее всех остальных, потому что и на верхней, и на нижней схеме чаша с этой монетой перевешивает.
|