Еще одна задачка на логику

[Ольга Ч.]

Улыбнёмся?
Вы попали в племя людоедов. Они очень желают Вас сожрать. Хитрый вождь племени решил развлечься и дал Вам «шанс»: «Произнеси любое утверждение. Если это утверждение будет истинным, то мы тебя сварим, если ложным – зажарим".
Есть ли у Вас шанс выжить?

[stas®]

Меня зажарят.

[Ольга Ч.]

А что будет с вождём после такого ответа?

[Настя]

С горя сварится

[P@vel]

Думаю утверждение - "вождь всегда прав", с ним вождь не сможет не согласиться.

[P@vel]

Согласен - ступил

[Минона]

Какая разница, в лоб, по лбу...Но шансы всегда есть. Не было ли в тот день лунного затмения?

[саня]

Улыбнёмся?
Вы попали в племя людоедов. Они очень желают Вас сожрать. Хитрый вождь племени решил развлечься и дал Вам «шанс»: «Произнеси любое утверждение. Если это утверждение будет истинным, то мы тебя сварим, если ложным – зажарим".
Есть ли у Вас шанс выжить?

вы меня зажарите,я бы так ответил

[MMM]

"Моё утверждение ложно" и всё.
В том смысле, что такое утверждение не может быть ни истинным, ни ложным, а значит, избавляемся и от варки, и от жарки...

[Чубчик]

А у меня такоу решение про взвешивание.
1. Делим на 5+5+2. Взвешиваем 5 _ 5.
1а) если равны - осталось одно взвешивание прочих 2 монет.
1б) если не равны - взвешиваем в "сомнительной" пятерке
2) 2 _ 2
2а) если равны - пятая монета фальшик
2б) если не равны - третье взвешивание из двух монет.
P.S. правда это решение подходит только если заранее известно, что фальшик либо легче либо тяжелее, а если не известно в которую сторону фальш, то ...

[Smic]

Вот такая "простая ветка", если же при первом взвешивании весы неравны, то это уже другая история

Т.е., метод работает с вероятностью 1/2, т.к. в "другой истории" к предложенному алгоритму требуется еще одно дополнительное взвешивание. Это не есть решение.

[Smic]

Интересно: если заранее известно, легче или тяжелее фальшивая монета, чем нормальная, то выбор за 3 взвешивания одной фальшивой можно осуществить из 27 монет

В 12.5% попыток

1 взвешивание: 4 и 4. Если равны - фальшивая в 4 оставшихся, если не равны - фальшивая в 8-ти взвешиваемых, из которых 4 назовём условно "тяжёлыми", а другие 4 условно "лёгкими".
Ветвеление 1. Если фальшивая в 4-х оставшихся -- сравниваем 2 из них с двумя нормальными,

2-е взвешивание. Независимо от его результата получим 2 монеты, одна из которых - плохая.

а затем одну из ненормальных с одной нормальной. (описано выше)

и 3-е взвешивание определит плохую монету.

Ветвление 2. На 1-ю чашу кладём 2 "лёгких" и 3 "тяжёлых" (запоминаем их), на 2-ю - 4 нормальных и 1 "тяжёлую".

2-взвешивание. И отложили 2 "легких" и 1 "тяжелую"

Если чаша с нормальными тяжелее, то выбор из 2 лёгких и 1 тяжёлой.

А если чаша в равновесии, то

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

это в худшем случае - 2 взвешивания. Итого - 4.

3 взвешивание: 1 лёгкая и 1 тяжёлая против 2-х нормальных (если выбор из 2+1),

в худшем случае 2 взвешивания

либо "тяжёлая" против "тяжёлой", если выбор из 3-х.

Если в этом случае весы не в равновесии, то потребуется еще одно (четвертое) взвешивание, что бы решить, какая монета плохая, сравнив одну из них с хорошей, в силу того, что нам не известен знак отклонения пв весе плохой монеты.

Всё.

Как видим, далеко не все...

[Smic]

Есть 12 монет, одна из которых отличается по весу. Надо при помощи 3 (трех) взвешиваний, определить, какая из них "плохая"
Так уточняю, мы не знаем сколько должна весить нормальная монетаВесы обычные равноплечие.
Задачка не так проста, как кажется

На самом деле задачка проста и сводится к задаче обычного бинарного (весы равноплечные) поиска одного элемента и множества N элементов. Для такой задачи известно, что если искомый элемент присутствует в множестве, то он может быть найден не более чем за Log(N) попыток, где логарифм берется по основанию 2 (поиск бинарный или двочный). В нашем случае множество состоит из 12-ти элементов, значит гарантировано "плохая" монета может быть найдена "чуть менее" чем за 4 попытки и "чуть более" чем за 3 попытки, т.е. за 4 попытки. А посему исходная задача (гарантированный поиск за 3 попытки) решения не имеет. За 3 попытки эту задачу можно решить только в случая некоторого везения, т.е. с определенной вероятностью, меньшей 1, или негарантированно.
Сама процедура бинарного поиска поиска в данной задаче выглядит так.
1 этап (не более 2-х взвешиваний) - сужение множества, содержащего плохую монету до 4-х элементов. Для этого делим монет на 3 равные кучи по 4 монеты. Взвешиваем 2 кучи из трех. Если весы в равновесии, то нам повезло и плохая монет находится в невзвешиваемой куче (мы сэкономили одну попытку, но вероятность такого везения -1/2). Если нет, то второе взвешивание гарантировано определит кучу с "плохой" монетой.
2 этап (не более 2-х взвешиваний) сужение множества, содержащего 4 монеты до искомой одной "плохой монеты". Сначала разделим чеиыре монеты на кучу из 3-х монет и одну "отложенную" монету. Далее для 3-монет используем алгоритм, аналогичный этапу 1, в котором слово "куча" заменено на слово "монета". При этом 2 взвешивания (3-е и 4-е) гарантировано покажут нам либо плохую монету (что и требовалось получить) либо ее отсутствие в куче из 3-монет. Но в последнем случае плохой будет "отложенная" монета, при этом мы не будем знать в какую сторону отличается ее вес от нормальной ( но этого исходная задача и не требовала), для этого потребуется дополнительное 5-е взвешивание.