Вот условие:
Есть 12 золотых и 12 серебряных монет. Одна из монет фальшивая (неизвестно, золотая или серебряная). Настоящие золотые монеты весят одинаково; настоящие серебряные тоже, но неизвестно, какие тяжелее (золотые или серебряные). Фальшивая золотая монета легче настоящих золотых, а фальшивая серебряная тяжелее серебряных. По виду можно сказать, золотая монета или серебряная, но нельзя сказать, настоящая или фальшивая. Сколько нужно взвешиваний, чтобы заведомо найти фальшивую монету?
Весы чашечные коромысла.
1) Я эту задачку решил так.
Монеты для шага 1: делим монеты на 3 кучки, в каждой по 4 золотых и серебряных. Взвешиваем любые две, назовем их кучка 1 и кучка 2.
Интерпретация взвешивания шага 1: если кучки равны, то фальшивка в третей кучке (4 золотых и 4 серебряных). Если не равны, то фальшивка либо в золотых монетах верхней чашки, либо в серебряных нижней чашки, то есть в этом случае мы можем сформировать кучку из 8 монет(4 золотых и 4 серебряных), где гарантированно будет фальшивка.
Монеты для шага 2: Берем нашу кучку с фальшивкой. Делим ее на три кучки: 2 золотых и серебряная, 2 золотых и серебряная и 2 серебряных. Взвешиваем кучку 1 и кучку 2.
Интерпретация взвешивания шага 2: если кучки равны, то фальшивка в третей кучке (2 серебряных). Если не равны, то фальшивка либо в золотых монетах верхней чашки, либо серебряная нижней чашки, то есть в этом случае мы можем сформировать кучку из 3 монет(2 золотых и серебряная), где гарантированно будет фальшивка.
Монеты для шага 3: если у нас после второго шага осталась кучка из двух серебряных, то все просто, просто будут две кучки по одной монете. Если у нас кучка из трех монет, (2 золотых и серебряная), то будем взвешивать по золотой монете, а серебряную отложим.
Интерпретация взвешивания шага 3: если взвешиваем серебро, то фальшивка в нижней чашке. Если взвешиваем золото и чашки равны, то фальшивка из серебра, иначе фальшивка в верхней чашке.
2) Сергей Фролов предложил следующий алгоритм:
Монеты для шага 1: делим монеты на 3 кучки, в каждой по 4 золотых и серебряных. Взвешиваем любые две, назовем их кучка 1 и кучка 2.
Интерпретация взвешивания шага 1: если кучки равны, то фальшивка в третей кучке (4 золотых и 4 серебряных). Если не равны, то фальшивка либо в золотых монетах верхней чашки, либо в серебряных нижней чашки, то есть в этом случае мы можем сформировать кучку из 8 монет(4 золотых и 4 серебряных), где гарантированно будет фальшивка.
Монеты для шага 2: Берем нашу кучку с фальшивкой. Делим ее на две кучки: 3 золотых и 3 серебряных и 1 золотая и серебряная. Также выделяем кучку из 3 золотых и 3 серебряных, которые заведомо настоящие. Взвешиваем кучку 1 и кучку 3.
Интерпретация взвешивания шага 2: если кучки равны, то фальшивка в второй кучке
(золотая и серебряная). Если не равны, то фальшивка либо в золотых монетах первой кучки, если чашка вверху, либо в серебряных первой кучки, если чашка внизу.
Монеты для шага 3: если у нас после второго шага осталась кучка из двух монет, то просто взвесим одну из монет с заведомо не фальшивой монетой того же материала. Если у нас кучка из трех монет, то будем взвешивать две монеты из этой кучки.
Интерпретация взвешивания шага 3: в первом случае, при равенстве чашек, то фальшивкой будет оставшиеся монета, при неравенстве, ее можно будет определить исходя из металла, который мы взвешивали. Во втором случае, если чашки равны, то фальшивкой будет оставшиеся монета, при неравенстве, ее можно будет определить исходя из металла, который мы взвешивали.
3) Способ предложил Руслан Батыров.
Поделим монеты на 12 кучек, по одной золотой и серебряной. Далее решаем задачу, следующим образом:
В качестве ответа мы получим, кучку и ее маркировку: Л или Т. Если Л, то фальшивка золотая, если Т, то серебряная.
4) Способ предложил Руслан Батыров.
Поделим монеты на 12 кучек, по одной золотой и серебряной. Теперь решаем задачу методом Дайсона.
В качестве ответа мы получим, кучку и ее маркировку: легкая или тяжелая. Если легкая, то фальшивка золотая, если тяжелая, то серебряная.
Дайсона, конечно метод универсальный, но понять идею лежащую за ним не легко. Насколько я понял, он не перекликается ни с одним вышеперечисленным методом.
Есть ли еще способы решить эту задачку? Какой из способов вам кажется наиболее понятным?
3) Способ предложил Руслан Батыров.
Поделим монеты на 12 кучек, по одной золотой и серебряной. Далее решаем задачу, следующим образом:
В качестве ответа мы получим, кучку и ее маркировку: Л или Т. Если Л, то фальшивка золотая, если Т, то серебряная.
4) Способ предложил Руслан Батыров.
Поделим монеты на 12 кучек, по одной золотой и серебряной. Теперь решаем задачу методом Дайсона.
В качестве ответа мы получим, кучку и ее маркировку: легкая или тяжелая. Если легкая, то фальшивка золотая, если тяжелая, то серебряная.
Дайсона, конечно метод универсальный, но понять идею лежащую за ним не легко. Насколько я понял, он не перекликается ни с одним вышеперечисленным методом.
Есть ли еще способы решить эту задачку? Какой из способов вам кажется наиболее понятным?
1) Нечестно посылать на метод Дайсона: выскакивает реклама, - смотрите её сами!
ReplyDelete2) Все методы непонятны, т.к. они типа "мне пришла в голову мысль такая-то для частного случая". А если мне не пришла? Лучше, если метод будет отталкиваться от известных способов для общего случая.
1) Ммм, не знаю о какой рекламе речь. Все ок по линку у меня
Delete2) Частный случай это какой? 24 монеты? В общем виде, задачу то никто и не собирался решать. Ну а если потребуется, то Дайсона метод поможет.
Интерпретация взвешивания шага 1: если кучки равны, то фальшивка в третей кучке (4 золотых и 4 серебряных). Если не равны, то фальшивка либо в золотых монетах верхней чашки, либо в серебряных нижней чашки, то есть в этом случае мы можем сформировать кучку из 8 монет(4 золотых и 4 серебряных), где гарантированно будет фальшивка.
ReplyDeleteЯ, все-таки, не понял как на первом этапе отобрали кучку с гарантированной фальшивкой. Фальшивка может быть и в верхней чаше весов и в нижней...