стояли звери около двери: задачка

[avva]

Красивая логическая задачка от Константина Кнопа. Я храбро бросился решать ее в уме и уже представлял, как напишу: "вот, красивая задачка, на бумаге легко, но интереснее ее в уме решить". А вот и фиг, не решилась она ни фига в уме. Но с ручкой и бумагой решилась.

Известно, что Крокодил всегда лжёт, Слон всегда говорит правду, Обезьяна просто повторяет чей угодно последний ответ, сказанный перед ней (а если ей задать самый первый из всех вопросов, ответит как попало), а Черепаха даёт честный ответ, но на предыдущий заданный ей вопрос (а на первый вопрос к ней отвечает как попало). Мудрый Крот наткнулся на Крокодила, Слона, Обезьяну и Черепаху, которые стояли друг за другом, и решил выяснить, в каком порядке они стоят.

Спросив их всех в порядке, в каком они стояли "Ты Крокодил?", он смог определить только где стоит Черепаха. Спросив всех в том же порядке: "Ты Черепаха?", он смог ещё понять, где стоит Крокодил, но полной ясности так и не наступило. И лишь после того, как на вопрос "Ты Обезьяна?" первый ответил "Да", Кроту наконец стало ясно, в каком порядке стояли животные. Так в каком же?

Comments

[rsokolov.livejournal.com]

"Sir, what is the practical application of this?" (c)

[levtsn.livejournal.com]

Неужели по голосу не понять кто крокодил, кто черепаха. )

[drhoenikker.livejournal.com]

Из последнего видно, что обезьяна первая (Слон не может врать, про остальных уже известно, так что их да не давало бы новой информации). Значит, предыдущий ответ был "Да". Так мог ответить только Крокодил, тк и Слон и Черепаха сказали нет.

В первом раунде должно быть ровно одно ДА, потому что если их нет, то вообще ничего не понять, а если два и понятно, где Черепаха, то понятно и где Обезьяна. Если бы Черепаха была бы на втором месте, то к концу второго раунда мы бы тоже знали, где Обезьяна. Значит, ОСЧК, и бумага не нужна. :)

[ger04ka.livejournal.com]

Вроде получилось в уме)
Обезьяна Крокодил Черепаха Слон.
Так?

[avva.livejournal.com]

Нет :)

[ger04ka.livejournal.com]

> В первом раунде должно быть ровно одно ДА, потому что если их нет, то вообще ничего не понять

Это неверное утверждение.
Наоборот, если в первом раунде 2 ДА, то в нем же однозначно определяется обезьяна (и второе ДА обязательно идет после первого).

[drhoenikker.livejournal.com]

Если это неверное утверждение, то какую именно информацию о местонахождении зверей вы получаете от первых 4ёх НЕТ?

[ger04ka.livejournal.com]

между 2 и 4 существуют ведь еще целые числа

[ger04ka.livejournal.com]

значит, не дорассмотрел случаи в уме, надо брать бумагу)

[(Anonymous)]

Мне кажется, что вместо
"...Черепаха даёт честный ответ, но на предыдущий..."
следует написать
"...Черепаха даёт честный ответ, но на последующий..."

[avva.livejournal.com]

Не могу понять: вы полагаете, что условие неправильное, и нужно было так (это неверно), или предлагаете изменить условие на такое, и тогда такой же ответ/другой ответ и тоже интересно (не думал об этом)?

[(Anonymous)]

Я не знаю, о чём вы. Если ответов ДА нет, то имеется ровно четыре НЕТ

[ger04ka.livejournal.com]

сорри, я был невнимателен, посыпаю голову и ем шляпу.
Прочитал слова "одно ДА" как "ДВА да".
Заодно нашел, где запутался у себя в уме.

[(Anonymous)]

Непонятно, как можно давать честный ответ на последующий вопрос, она же его не знает.

[dims12.livejournal.com]

Решал около часа, старался в уме. Несколько раз менял ход рассуждений, но всё время только писал в этой клеточке словесный текст, без формул и других вспомогательных надписей.

В конце концов, пришёл к выводу, что фишка в том, что не надо пытаться повторять рассуждения Крота на первом этапе. Они возможны (Крот-то их проделал), но для нас они слишком сложны, так как мы не знаем ответов. Нам нужно перебрать множество ответов и вычислить, в каких случаях Черепаха раскрывает себя, а это без бумажки не получится.

Если же двигаться от конца, то удаётся получить упрощения, которые позволяют вычислить в уме, что произошло на первом вопросе и как Крот вычислил Черепаху.

***

Общее свойство: если в цепочке ответов нет повторов, то Обезьяна стоит первая, так как она обязательно даёт повтор. Поскольку на всех этапах положение Обезьяны было неизвестно, то в ответах были повторы, которые давали основание предполагать, что их даёт Обезьяна.

На этапе последнего вопроса, Крот знает, где Крокодил и Черепаха, так же, он он знает, какие ответы поступят из их местоположений: Крокодил всегда лжёт и ответит "нет", а Черепаха отвечает с запаздыванием, но Крот знает, какие вопросы он задавал раньше (мы ответ не знаем, Крот знает).

При этом, ответ первого животного в цепочке был Кроту неизвестен, иначе он не мог быть ключом к разгадке. Значит, это не Крокодил и не Черепаха (их ответы известны и ключом быть не могут). То есть, на первом месте могли быть Слон или Обезьяна. Но Слон честен и он бы ответил "нет", а прозвучал ответ "да". Стало быть, на первом месте была Обезьяна и это выяснилось только на последнем ответе.

Теперь отходим на один вопрос назад. Крот знает, что должны ответить Крокодил ("да"), Слон ("нет") и Черепаха ("нет"). Если бы стоящая впереди Обезьяна ответила бы "да", то Крокодила нельзя было бы найти, где бы он ни стоял. Но Крот его нашёл. Стало быть, он единственный ответил "да", а Обезьяна ответила "нет".

Эти 4 известные ответа надо расположить так, чтобы были повторы, потому что при отсутствии повторов, Крот сразу догадался бы, что Обезьяна стоит впереди. Стало быть, это "нет", "нет", "да", "нет", то есть, Крокодил находится на третьем месте.

Наконец, переходим к первому вопросу. Ответы Крокодила и Слона известны и это "нет" у обоих, причём Слон расположен на втором или четвёртом месте и поэтому обязательно составляет повтор с Крокодилом. Если бы в цепочке был всего один этот повтор, то его нельзя было бы списать на обезьяну и нужен ещё. То есть, должно быть либо три "нет" в начале и одно "да" в конце, либо три "нет" подряд в конце, либо два "да" в начале и два "нет" в конце.

Но в последних двух случаях нельзя было бы вычислить Черепаху, а Крот её вычислил. Стало быть, первые ответы были "нет", "нет", "нет", "да", Черепаха выдала себя случайным ответом.

Слон, стало быть, на втором месте.

[(Anonymous)]

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

По условию задачи, кот смог узнать только черепаху, и он мог её узнать только если она сказала да. Если бы да было сказано два раза подряд, то он узнал бы еще и обезьяну, а если бы эти да были первыми, то он не смог бы определить, кто стоит первым - черепаха или обезьяна.

Таким образом мы узнаем что черепаха не стоит за обезьяной

[(Anonymous)]

На второй вопрос крокодил скажет да, слон скажет нет. Черепаха скажет нет, отвечая на первый вопрос. Обезьяна, если стоит первой, скажет либо да либо нет. Если за крокодилом - то да. Если за слоном или черепахой - то нет.

Кот смог найти крокодила, который сказал да. Он не смог найти обезьяну, значит обезьяна не стоит за крокодилом тоже.

Обезьяна стоит либо первой либо за слоном.

[etot-samyi.livejournal.com]

Нашел аналогичную задачу в задачнике для олимпиады для 6-7х классов :)
http://mathus.ru/math/matholymp67.pdf
Номер 4.3.31

[(Anonymous)]

Сорри. Час ночи у нас, туплю

В общем еще раз

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

Если бы обезьяна стояла первой, она могла бы сказать да, а черепаха могла бы сказать нет и определить, кто из них сказал да было бы нельзя. Значит первый ответ был нет и там не могло стоять черепахи.

Итак мы узнали, что черепаха вторая, третья или четвёртая и обезьяна за ней не стоит.

[(Anonymous)]

На второй вопрос обезьяна повторит ответ последнего животного на первый вопрос. Крокодил скажет да, слон скажет нет. Черепаха скажет нет, отвечая на первый вопрос.

Кот узнал крокодила, который сказал да.

Если бы обезьяна стряла за крокодилом, то кот узнал бы и её, однако этого не произошло. Следовательно обезьяна либо стоит первая либо находится за слоном.

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

[(Anonymous)]

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

Мы знаем, что черепаха не стоит на первом месте, так как иначе кот бы её не узнал после первого вопроса. Крокодил тоже не может стоять на первом месте, так как кот уже знает где он и этот ответ не добавил бы ничего нового.

Следовательно обезьяна стоит первой. Крокодил находится на четвёртом месте.

[(Anonymous)]

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

Поскольку кот не смог опредедить её местонахождение с двух вопросов и ему потребовался третий, то черепаха должна была быть на третьем месте.

Таким образом итоговая последовательность: обезьяна, слон, черепаха и крокодил.

[(Anonymous)]

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

[winnie-olga.livejournal.com]

Решала в уме.
Получилось так: Обезьяна, (Слон, Черепаха), Крокодил.
Слон и Черепаха могут быть в любом порядке, все зависит от их ответов на первый вопрос.

Рассуждаем с конца:
1) На вопрос «Ты обезьяна?» 1 ответил Да. Так могли ответить Обезьяна (номер 4 до этого на вопрос «Ты черепаха?» ответил Да), крокодил (всегда лжет) или черепаха (потому что она в этом случае отвечает на пред. вопрос «Ты черепаха?») . Итак, обезьяна, крокодил или черепаха. И после этого ответа кроту все стало понятно. Но к этому времени он уже знал, где стоят черепаха крокодил. Делаем вывод, что по этому вопросу-ответу крот узнал обезьяну.
Итак, обезьяна — 1.

2) Обезьяна стоит на 1 месте и отвечает Да на вопрос «Ты обезьяна?» . Следовательно на 4 месте до этого на вопрос «Ты черепаха?» ответили Да. Кто мог так ответить? Слон — не мог. Крокодил — мог. Черепаха не могла, потому что в этом случае она бы отвечала на вопрос «Ты крокодил?» и сказала бы Нет. Вывод: на 4 месте стоит крокодил.
Итак, крокодил — 4.

обезьяна X Y крокодил

3) Как по вопросу «Ты Черепаха?» крот смог определить крокодила? Слон ответит Нет, крокодил ответит Да, черепаха ответит Нет. Что ответит обезьяна? Она повторит ответ крокодила на вопрос «Ты Крокодил?», т. е. тоже Нет. Значит, только крокодил ответит Да.

4) Думаем, как по первому вопросу «Ты крокодил?» он смог определить черепаху? Слон и крокодил на этот вопрос точно ответят Нет, т. е. в ответах будет два Нет. Если бы все ответили Нет, то определить ничего не выйдет.
Есть вариант Да Да Нет Нет, но тогда непонятно, кто из Да есть черепаха, а кто обезьяна.
Определить кого-то можно, только если ответы идут в порядке Нет, Да. Если после Нет появляется Да, то это может быть только черепаха, потому что обезьяна тоже ответила бы Нет.
Крокодил — 4, так что это Нет отпадает. Варианты: обезьяна сказала Нет и получилось
Нет (обезьяна) Да (черепаха) Нет (слон) Нет (крокодил)
или слон сказал Нет и получилось
Нет/Да (обезьяна) Нет (слон) Да (черепаха) Нет (крокодил)

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

обезьяна черепаха слон крокодил
нет да нет нет → черепаха = 2 "Ты Крокодил?"
нет нет нет да → крокодил = 4 "Ты Черепаха?"
да → обезьяна = 1 "Ты Обезьяна?"

обезьяна слон черепаха крокодил
нет нет да нет → черепаха = 3 "Ты Крокодил?"
нет нет нет да → крокодил = 4 "Ты Черепаха?"
да → обезьяна = 1 "Ты Обезьяна?"

[tyomitch.livejournal.com]

Если бы Черепаха была бы на втором месте, то к концу второго раунда мы бы тоже знали, где Обезьяна.

Откуда бы мы это знали?
Либо она первая, и собезьянничала за Крокодилом из прошлого раунда; либо она третья, и собезьянничала за Черепахой.