?

Log in

No account? Create an account
стояли звери около двери: задачка - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

стояли звери около двери: задачка [янв. 24, 2018|12:26 pm]
Anatoly Vorobey
[Tags|]

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

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

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

Comments:
Страница 1 из 2
<<[1] [2] >>
[User Picture]From: rsokolov
2018-01-24 10:49 am
"Sir, what is the practical application of this?" (c)
(Ответить) (Thread)
[User Picture]From: levtsn
2018-01-24 11:19 am

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

(Ответить) (Thread)
From: drhoenikker
2018-01-24 11:22 am
Из последнего видно, что обезьяна первая (Слон не может врать, про остальных уже известно, так что их да не давало бы новой информации). Значит, предыдущий ответ был "Да". Так мог ответить только Крокодил, тк и Слон и Черепаха сказали нет.

В первом раунде должно быть ровно одно ДА, потому что если их нет, то вообще ничего не понять, а если два и понятно, где Черепаха, то понятно и где Обезьяна. Если бы Черепаха была бы на втором месте, то к концу второго раунда мы бы тоже знали, где Обезьяна. Значит, ОСЧК, и бумага не нужна. :)
(Ответить) (Thread)
From: ger04ka
2018-01-24 11:39 am
> В первом раунде должно быть ровно одно ДА, потому что если их нет, то вообще ничего не понять

Это неверное утверждение.
Наоборот, если в первом раунде 2 ДА, то в нем же однозначно определяется обезьяна (и второе ДА обязательно идет после первого).
(Ответить) (Parent) (Thread) (Развернуть)
From: ger04ka
2018-01-24 11:35 am
Вроде получилось в уме)
Обезьяна Крокодил Черепаха Слон.
Так?
(Ответить) (Thread)
[User Picture]From: avva
2018-01-24 11:36 am
Нет :)
(Ответить) (Parent) (Thread) (Развернуть)
From: (Anonymous)
2018-01-24 11:48 am
Мне кажется, что вместо
"...Черепаха даёт честный ответ, но на предыдущий..."
следует написать
"...Черепаха даёт честный ответ, но на последующий..."
(Ответить) (Thread)
[User Picture]From: avva
2018-01-24 11:49 am
Не могу понять: вы полагаете, что условие неправильное, и нужно было так (это неверно), или предлагаете изменить условие на такое, и тогда такой же ответ/другой ответ и тоже интересно (не думал об этом)?

Edited at 2018-01-24 11:50 (UTC)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: dims12
2018-01-24 12:48 pm
Решал около часа, старался в уме. Несколько раз менял ход рассуждений, но всё время только писал в этой клеточке словесный текст, без формул и других вспомогательных надписей.

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

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

***

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

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

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

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

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

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

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

Слон, стало быть, на втором месте.
(Ответить) (Thread)
[User Picture]From: mtyukanov
2018-01-24 02:20 pm
При ответах на второй вопрос "нет, нет, да, нет", обезьяна должна была бы на третий вопрос ответить "нет".
(Ответить) (Parent) (Thread) (Развернуть)
From: (Anonymous)
2018-01-24 01:00 pm
На первый вопрос крокодил и слон ответят нет, черепаха ответит либо да либо нет, обезьяна, если стоит первой - либо да либо нет, если за слоном или крокодилом, то нет, если за черепахой - то повторит ее ответ.

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

Таким образом мы узнаем что черепаха не стоит за обезьяной
(Ответить) (Thread)
From: (Anonymous)
2018-01-24 01:07 pm
На второй вопрос крокодил скажет да, слон скажет нет. Черепаха скажет нет, отвечая на первый вопрос. Обезьяна, если стоит первой, скажет либо да либо нет. Если за крокодилом - то да. Если за слоном или черепахой - то нет.

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

Обезьяна стоит либо первой либо за слоном.
(Ответить) (Parent) (Thread) (Развернуть)
From: etot_samyi
2018-01-24 01:16 pm

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

Edited at 2018-01-24 13:28 (UTC)
(Ответить) (Thread)
[User Picture]From: spamsink
2018-01-24 03:30 pm
Вот именно. С ёжиком в тумане и жирафом куда как красивее, а это выглядит как жалкий плагиат.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2018-01-24 01:49 pm
обезьяна первая, за ней слон, черепаха, крокодил
На первый вопрос может быть только одно да - от черепахи, если у нас два да - от черепахи и обезьяны, то мы либо однозначно определяем обоих, либо не можем определить ни одну из них.
На второй вопрос крокодил отвечает да, черепаха и слон - нет. Если обезьяна отвечает да, то аналогично, мы либо можем однозначно определить где стоит обезьяна, либо не можем определить где стоит крокодил.
При этом точно известно, что обезьяна не стоит за черепахой (и не стоит на первом месте, если черепаха на последнем) и не стоит за крокодилом.
Т.е. черепаха и крокодил стоят последними, а слон с обезьяной первыми.
На третий раз поскольку первый отвечает да - то это обезьяна, за ней идёт слон, потом черепаха (которая на предыдущем вопросе сказала нет) и крокодил (который сказал да, которое повторила обезьяна)





(Ответить) (Thread)
[User Picture]From: winnie_olga
2018-01-24 01:54 pm
Решала в уме.
Получилось так: Обезьяна, (Слон, Черепаха), Крокодил.
Слон и Черепаха могут быть в любом порядке, все зависит от их ответов на первый вопрос.

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

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

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

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

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

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

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

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

(Ответить) (Thread)
From: (Anonymous)
2018-01-24 02:26 pm
обезьяна черепаха слон крокодил не проходит.
После ответа на первый вопрос уже ясно, что обезьяна не третья (она бы тоже ответила "да"). Тогда после второго вопроса порядок становится однозначным (или очск, или счок, но, опять же, второй вариант не подходит), и третий вопрос не нужен.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: son_0f_morning
2018-01-24 02:19 pm

Пока не решил

В уме действительно интересно!

На бумажке просто выписать 24 варианта расстановок животных и механически проверить.

Edited at 2018-01-24 14:20 (UTC)
(Ответить) (Thread)
[User Picture]From: psilogic
2018-01-24 07:24 pm

RE: Пока не решил

По правилам подходит сразу несколько, как минимум: ОЧСК, ОCЧК и СОЧК.
Поэтому не обойтись без рассуждений типа "Крот мог узнать/Крот не мог узнать"
(Ответить) (Parent) (Thread) (Развернуть)
From: (Anonymous)
2018-01-24 05:31 pm
Крокодил обезьяна слон черепаха
(Ответить) (Thread)
From: (Anonymous)
2018-01-25 04:20 am
путин бомба героин кухня спички керосин
(Ответить) (Parent) (Thread)
[User Picture]From: p_govorun
2018-01-24 06:07 pm
...И лишь после того, как на вопрос "Ты Обезьяна?" первый ответил "Да", Кроту наконец стало ясно, в каком порядке стояли животные.

И тогда Майя Тойвовна Глумова закричала.
(Ответить) (Thread)
[User Picture]From: dreamer_other
2018-01-24 06:51 pm
О, С, К, Ч
Рассуждение:
К 3му вопросу 1я буква была неизвестна, иначе вопрос бы не требовался. О не может быть после К и Ч, тк тогда О была бы известна после 2го и С соответственно тоже. Значит К и Ч могут занимать только 3 и 4 позиции. На 3й вопрос С ответил бы Нет, значит первая О. Теперь надо понять, КЧ или ЧК. Точного решения нет, однако, если ЧК, тогда после первого вопроса будет известно, что О на 1 или 2, тогда, наверно, 2м вопросом можно что-то спросить по другому и узнать решение сразу без 3го.
(Ответить) (Thread)
[User Picture]From: dreamer_other
2018-01-24 07:22 pm
Прочитал комменты и понял, что упустил, что О рандомит только первый раз на первом месте, а потом всегда повторяет. Значит на 2й вопрос К должен быть на последнем месте и ответить Да, что бы обезьяна повторила это Да на 3м вопросе. Ну все равно не обидно, тк тут скорее неясность в условии :)
(Ответить) (Parent) (Thread)
[User Picture]From: psilogic
2018-01-24 07:32 pm
У меня получилось понять, как Крот "все понял", но не получилось понять, как все понять нам :)

Сокращаю Д(да),Н(нет), животных как ЧОСК.

На вопрос "ты крокодил?" животные должны ответить:
С = Н
К = Н
О = random в позиции 1, иначе как предыдущий
Ч = random

Количество Д = 0..2
- Допустим, количество Д = 0. Серия ответов НННН допускает расстановки ЧОСК и ОЧСК, что не позволит Кроту установить позицию Ч, значит количество Д не 0.
- Допустим, количество Д = 2. Если есть соседние НД, то Ч на месте Д (обезьяна не смогла бы не собезьянничать). Тогда второе Д, укажет на О. Но Крот не узнал после 1 вопроса, где О. Значит среди серий с 2Н и 2Д, допускаются только серии без соседних НД. Такая только одна: ДДНН. Но она допускает расстановки ЧОСК и ОЧСК, что не позволит Кроту установить позицию Ч, значит количество Д не 2.
- Значит, количество Д = 1. По единственному Д Крот нашел Ч.
- Серия ДННН допускает расстановки ЧСКО и ОКСЧ, что не позволит Кроту установить позицию Ч.
- Остаются серии:
НДНН, ННДН, НННД - т.е. Ч точно не первая.

На вопрос "ты черепаха?" животные должны ответить:
С = Н
К = Д
О = как предыдущий
Ч = Н (отвечая на предыдущий вопрос)

Что ответила О?
Если она ответила Д, тогда остается только два Н, одно принадлежит Ч, второе - С. Зная позицию Ч, Крот вычислит позицию С, а он на этом шаге не нашел С. Значит О ответила Н. Значит и во сторой серии будет только один ответ Д, и по нему Крот вычислил К(рокодила). Варианты серий ответов:

ДННН, НДНН, ННДН, НННД

На вопрос "ты обезъяна?" животные должны ответить:

С = Н
К = Д
О = как предыдущий
Ч = Д (отвечая на предыдущий вопрос)

Кроту хватило здесь только первого вопроса. Это не мог быть ответ К или Ч, поскольку их позиции уже были известны Кроту, их ответы тоже заранее известны и никакой новой инфы он из этого ответа не получил бы.

Далее, важен последний ответ предыдущей серии.

Если он был Н, тогда первый ответ третьей серии будет Н и для О, и для С. Значит опять - никакой инфы.

Допустим, последний ответ второй серии был Д. Теперь, если первый ответ третьей серии Н, то это однозначно С, а если первый ответ третьей серии Д, то это однозначно О. Действительно, в этом и только в этом случае из одного первого ответа можно вытащить достаточно инфы. А это значит, что из вариантов второй серии остается только НННД. Крокодил - последний.

Посмотрим, какие остались варианты:

Первая серия: НДНН, ННДН, НННД
Вторая серия: НННД
Третья серия: Н, Д

В первой серии позиция Д определяет положение Ч. Поскольку выяснилось, что К - последний, то третий вариант первой серии отпадает. Ч - либо вторая, либо третья. Остается:

Первая серия: НДНН, ННДН
Вторая серия: НННД
Третья серия: Н, Д

Остается всего 4 комбинации:
НДНН->НННД->Н
ННДН->НННД->Н
НДНН->НННД->Д
ННДН->НННД->Д
Первая серия определяет положение Ч, вторая положение К (всегда последний), третья, кто первый - С или О. То есть напротив каждой комбинации можно выписать расстановку:

НДНН->НННД->Н = CЧОК
ННДН->НННД->Н = СОЧК
НДНН->НННД->Д = ОЧСК
ННДН->НННД->Д = ОСЧК

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

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

То есть у меня получается, что, хотя Крот действительно однозначно все вычислил на третьем вопросе, но нам не хватает данных.

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


Edited at 2018-01-24 19:38 (UTC)
(Ответить) (Thread)
[User Picture]From: dreamer_other
2018-01-24 07:45 pm
СОЧК: C не может быть первым, тк на 3й вопроc он ответил бы "Нет".
ОЧСК: Если после 2го вопроса расположение _Ч_К, то Крот догадался бы, что после Ч не О, так как был бы дубль "Да". А значит он бы уже знал решение и 3й вопрос не потребовался бы.
(Ответить) (Parent) (Thread)
Страница 1 из 2
<<[1] [2] >>