Эта история случилась давным-давно, еще во времена крестовых походов. Один из рыцарей был захвачен мусульманами в плен и предстал перед их предводителем - султаном Саладином, который объявил, что освободит пленника и его коня, если получит выкуп в 100 тысяч золотых монет. "О, великий Саладин, - обратился тогда к султану рыцарь, у которого за душой не было ни гроша, - ты лишаешь последней надежды. У меня на родине мудрому и находчивому пленнику дается шанс выйти на свободу. Если он решит заданную головоломку, его отпускают на все четыре стороны, если нет - сумма выкупа удваивается!"
"Да будет так, - ответил Саладин, и сам обожавший головоломки. - Слушай же. Тебе дадут двенадцать золотых монет и простые весы с двумя чашками, но без гирь. Одна из монет фальшивая, однако неизвестно, легче она или тяжелее настоящих. Ты должен найти ее всего за три взвешивания. Hе справишься с задачей до утра - пеняй на себя!" А вы смогли бы выкрутиться?
Ответ: Эта задача была блестяще разобрана К. Л. Стонгом в майском номере журнала 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, вы кладете на правую чащу весов. Таким образом вы узнаете последнюю цифру нужного вам числа.
Комментарии
Решение неправильно. По условию неизвестно тяжелее или легче фальшивая монета, а в решении, в этой строке "Если перевесит левая чашка, то искомое число начинается с 0, а если правая - то с 2." уже подразумевается , что фальшивая - тяжелее.
Я вообще не в курсе что такое троичная система. Не нужно тут ничего заумного делать. делим на три четверки, взвешиваеи одну против другой. Если равно,то значит в третьей четверке - брак. берем 3 монеты из 3-й четверки, и три любые с весов, и взвещиваем друг против друга. Если равно - то брак в руке. Если нет, то берем из "бракованной" тройки две монеты и взвешиваем друг против друга. Если равно - брак в руке. Если перевес - то брак тот, который сответствует чашке с браками во время взвешивания троек.
Если же при первом взыешивании четверки не уравнялись, то тогда берем с правой чашки 2 моеты и убираем на стол. Оставшиеся 2 монеты перекладываем на противоположную чашу, а оттуда сюда перекладываем 1 монету, и доббавляем всю "хорошую" четверку. Получилось 5 против пяти. Если уравнялось, то проблема в отложенных 2-х монетах. На третьем взвешивании заменим одну из монет на любой чаше монетой со стола. Если ровно - брак в руке, если же не ровно - брак на чаше.
Если же 5 против 5 остались в том же положении, значит проблема в тех трех монетах, которые мы не перекладывали, и тогда взвешиваем из этой тройки 1-1. ровно - брак третья монета. Не ровно - брак - та монета, которая соответствует позиции 5-5.
Если же 5-5 чаши перевесились в противоположную сторону, то проблема в оставшихся трех монетах ( 1 переложенная СЮДА, и 2, переложенные ТУДА. Взвешиваем 2 монеты , которые мы переложили ТУДА друг против друга. Ровно - брак оставшаяся монета. Неровно - брак та монета, позиция которой соответствует позиции 5-5.
Вот так .
В ответе подразумевается, что фальшивая монета тяжелее, тогда решение действительно будет в 3 взвешивания и без всяких троичных систем. Т.е. первое взвешивание: берем по 6 монет и выбираем кучку по тяжелее. второе взвешивание: делим тяжелую кучку по 3 монеты и выбираем опять же по тяжелее. третье взвешивание: берем 2 монеты из 3-х и взвешиваем их между собой, тогда при равенстве - фальшивая монета - 3-я, при неравенстве - фальшивая монета тяжелее.
Мне кажется что проще будет так: Берем эти 12 монет и делим на две кучки по 6.. Расмотрим первую шестерку: ложим на каждую сторону весов по 3 монеты то может получиться два варианта:
1) если кучки равны то значит в этой шестерке все монеты настоящие, тогда беремся за вторую шестерку.. Сравнивем ее с первой и смотрим какая из куче весит больше.. Если первая то подделка весит легче, если вторая то подделка вести больше...
2) если кучки не равны то значит во второй шестерке все монеты настоящие, тогда сравнием первую шестерку со второй и смотрим что больше весит.. Если первая то потделка тяжелее, если вторая то потделка легче.
Разбили на 3 кучки по 4 монеты,взвесили любые две:
1.равновесны - значит обе из настоящих,убираем с одной из чаш 4 монеты и кладём другие.Делаем выводы в зависимости от положения чаш о весе фальшивки.
2.неравновесны - в одной чаше фальшивка,запоминаем положение чаш относительно друг друга и меняем содержимое одной чаши:
а)уравнялись - значит фальшивка была до обмена,вспоминаем где находилась чаша до обмена и делаем выводы о весе фальшивки
б)не уравнялись - значит мы поменяли настоящие на настоящие,опять таки делаем вывод о весе фальшивки по положению чаш.
Вот Вам аж 4 варианта решений: http://igoresz.narod.ru/12
Делим на три кучки A,B и С по четыре монетки в каждой. A - [A1/A2/A3/A4], B - [B1/B2/B3/B4], C- [C1/C2/C3/C4].
Вариант №1
1) За первое взвешивание выявляем эталонную четверку [ЭЭЭЭ], взвешиваем кучки A и B, если вес одинаковый A=B (следовательно) фальшивка в кучке C, а кучки А или B становятся эталонными Э. За следующие два взвешивания узнаем, какая именно монета является эталонной.
2) Во втором взвешивании сравниваются 3-и монеты из кучки С [С1/С2/С3] и 3-и монеты из эталонной кучки [Э/Э/Э]. Если “равно”, то фальшивка С4. Если тяжелее (или легче), то фальшивка в кучке и С [С1/С2/С3] и эта фальшивка тяжелая (или легкая).
3) В третьем взвешивании сравниваем любые две монеты из кучки С [С1/С2/С3] между собой если вес одинаковый, то фальшивка не взвешивалась, а если чаши перевесились то фальшивка одна из двух та, которая тяжелая (или легкая).
Вариант №2
1) За первое взвешивание опять выявляем эталонную четверку [ЭЭЭЭ], взвешиваем кучки A и B, если вес не равен A>B (или A
2) Во втором взвешивании сравниваются [A1/Э/Э/Э] и [B1/A2/A3/A4 ] (не используются: B2/B3/B4).
3.1) Если вес одинаковый, то фальшивка находится среди неиспользованных монеток B2/B3/B4 и в данном случае эта троица из лёгкой кучки [B1/B2/B3/B4]. То есть лёгкая фальшивка в этой тройке должна быть найдена среди B2/B3/B4. Значит надо взвесить любые две монет из этой тройки и если одна легче то она фальшивка. Если обе монеты равны, то фальшивка оставшаяся монета.
3.2) Если неравенство первого взвешивания не изменилось, то есть «передвижения монет» никак не повлияли на результат (направление неравенства, чашка не перевесила) второго взвешивания, то значит изменившие свои места монетки A2/A3/A4 никак «не сыграли», и ни одна из них не является фальшивой, то есть фальшивка A1 или B1. В третьем взвешивании любую из этих двух монет сравниваем с одной эталонной, если монета тяжелее или легче чем эталонная то она фальшивая, а если нет разницы, то фальшивка оставшаяся монета.
3.3) Если неравенство первого взвешивания изменилось, то есть передвижения монет повлияли на результат второго взвешивания (чашка перевесила), то значит изменившие свои места монетки A2/A3/A4 сыграли и фальшивка среди них. Как мы уже выше определились кучка A тяжелее, A1 нефальшивая, значит именно тяжелая фальшивка среди троицы A2/A3/A4, Значит надо взвесить любые две монет из этой тройки и если одна легче то она фальшивка. Если обе монеты равны, то фальшивка оставшаяся монета
Вариант №3
1) За первое взвешивание опять выявляем эталонную четверку [ЭЭЭЭ], взвешиваем кучки A и B, если вес не равен A>B (или A
2) Во втором взвешивании сравниваются [A1/A2/B1] и [B2/A3/A4] (не используются: B3/B4).
3.1) Если вес одинаковый, то фальшивка находится среди неиспользованных монеток B3/B4, значит, в третьем взвешивании любую из этих двух монет сравниваем с одной эталонной, если монета тяжелее или легче чем эталонная то она фальшивая, а если нет разницы, то фальшивка оставшаяся монета.
3.2) Если неравенство первого взвешивания не изменилось, то есть «передвижения монет» никак не повлияли на результат (направление неравенства, чашка не перевесила) второго взвешивания, то значит, изменившие свои места монетки A3/A4 и B1 никак не сыграли, и ни одна из них не является фальшивой. То есть фальшивка среди монеток, которые не меняли места A1/A2 и B2. Третье взвешивание сравнение тяжелых A1 и A2 и если одна тяжелее то она фальшивка. Если обе монеты равны, то фальшивка оставшаяся монета B2.
3.3) Если неравенство первого взвешивания изменилось, то есть передвижения монет повлияли на результат второго взвешивания (чашка перевесила), то значит изменившие свои места монетки A3/A4 и B1 сыграли и фальшивка среди них. Третье взвешивание сравнение тяжелых A3 и A4 и если одна тяжелее то она фальшивка. Если обе монеты равны, то фальшивка оставшаяся монета B1.
Для Lynx: жаль, что Ваш алгоритм показан не полностью... Та самая интересная часть (у вас это "Вариант №2"), когда две кучки в первом взвешивании "не равны" по весу как раз отсутствует (не "вписался полностью").
Что касается "Вариант №1" то и здесь есть "альтернатива" :) C1C2C3C4-содержит фальшивку... тогда
(2) сравним С1С2 с 2эталонами...
... и Если <>, тогда... фальш в этой паре...
(3) сравним С1 и Э (если <>, то С1, если =, то С2.
... или Если =, тогда... фальш другой паре...
(3.1) сравним С3 и Э (если <>, то С3, если =, то С4.
В догонку, если вам интересен тот "Вариант№2", который позволяет сразу "потратить" эталоны, то можно решить и так. :) см. ссылку ниже.