ИТ-сообщество г. Волгодонск

Общие => Флейм => Тема начата: kabyzdoh от 05 Марта 2007, 22:30:24

Название: Задача про три автомата
Отправлено: kabyzdoh от 05 Марта 2007, 22:30:24
Есть три автомата, один всегда говорит правду, второй всегда лжет, третий "поломанный" - иногда говорит правду, иногда лжет. Необходимо, задав три вопроса, выяснить кто есть кто. Один вопрос можно задать одному любому автомату. Задача простая, но кому ни задавал, все испытывают затруднения при ее решении.
Название: Re: Задача про три автомата
Отправлено: Uppum от 06 Марта 2007, 00:16:18
Есть решение. Но задача не простая :)
Предлагю обментся решениями :)
Мое решение работает 100 % :)
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 06 Марта 2007, 11:03:41
Важное уточнение: автоматы могут ответить только "Да" или "Нет"!
Название: Re: Задача про три автомата
Отправлено: point212 от 06 Марта 2007, 11:29:41
Так я не понял, третий автомат говорит с вероятностью 50% или вообще от фонаря?
Все равно не знаю как решить.

Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 06 Марта 2007, 11:39:02
Есть три автомата, один всегда говорит правду, второй всегда лжет, третий "поломанный" - иногда говорит правду, иногда лжет. Необходимо, задав три вопроса, выяснить кто есть кто. Один вопрос можно задать одному любому автомату. Задача простая, но кому ни задавал, все испытывают затруднения при ее решении.
Важное уточнение: автоматы могут ответить только "Да" или "Нет"!
. Поломанный автомат говорит "Да" или "Нет" от фонаря.
Название: Re: Задача про три автомата
Отправлено: point212 от 06 Марта 2007, 11:47:36
Ха... ну тогда хз. С тремя вопросами не разберешься.
Название: Re: Задача про три автомата
Отправлено: Uppum от 06 Марта 2007, 12:15:00
Есть решение :) Кабыздох !!! Давай свое решение :) Или у тебя его нету :))))
Название: Re: Задача про три автомата
Отправлено: DoReMi от 06 Марта 2007, 12:22:33
А какого рода вопросы? Можно ли у второго спрашивать "Врет ли первый?"
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 06 Марта 2007, 12:24:50
А какого рода вопросы? Можно ли у второго спрашивать "Врет ли первый?"
Любые, которые подразумевают однозначный ответ.
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 06 Марта 2007, 12:25:40
Есть решение :) Кабыздох !!! Давай свое решение :) Или у тебя его нету :))))
Пиши в личку.
Название: Re: Задача про три автомата
Отправлено: point212 от 07 Марта 2007, 14:50:36
Кабыздох... пора выкладывать решение... ибо народ так ничего и не предложил
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 07 Марта 2007, 14:59:09
Кабыздох... пора выкладывать решение... ибо народ так ничего и не предложил
Два дня всего теме. Может еще кто-то решит.
Название: Re: Задача про три автомата
Отправлено: DoReMi от 07 Марта 2007, 15:13:12
Интернет большой, однако. А чукча умный, он гуглит.
Кстати, все три вопроса, судя по интернету можно задавать не обязательно всем подряд, а только одному или двум, или сначала первому, потом второму, потом снова первому.
Если это так - должно быть определено в условии.
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 07 Марта 2007, 15:17:38
Я писал "Один вопрос можно задать одному любому автомату" - вроде как все этим сказано. Т.е. любой из 3 вопросов  можно задать только ОДНОМУ, НО ЛЮБОМУ из трех автомату
Название: Re: Задача про три автомата
Отправлено: Dio от 07 Марта 2007, 16:08:15
2+2=4?
2+3=5?
тот кто сказал нет(если оба то о любом спросить) иногда обманывает?
Название: Re: Задача про три автомата
Отправлено: DoReMi от 07 Марта 2007, 16:36:22
Если вопрос ставить образом "Ты (другой автомат) всегда говоришь(-ит) правду?" то получается картина:

1. В случае "ты" ответ "нет" имеет смысл только для рандомно отвечающего автомата:
а) правдивый автомат не может сказать "нет, я говорю неправду"
б) лживый автомат конечно же скажет "да, я говорю только правду"
- таким образом, я думаю вопрос "ты" не актуален.

2. В случае "другой" ответ "да" имеет смысл только для лживого и рандомно отвечающего автомата, а ответ "нет" имеет смысл для правдивого и рандомно отвечающего автомата, при этом теряется важность вопроса о ком мы спрашиваем, о соседе слева или о соседе справа, ответ будет тем же
- таким образом, кажется можно решить задачу.

Нет... в любом случае мы можем получить варианты "Да,Да, Нет" и "Нет,Нет,Да".
Если одно "Нет", то это ответ правдивого, но надо различить лживого и рандомного.
Если одно "Да", то это ответ лживого, но надо различить правдивого и рандомного.
А у нас лимит вопросов уже исчерпан.
Значит все же надо возвращаться к вопросу личному... Только там мы разделим рандом и не рандом. Надо строить последовательность обхода в зависимости от ответа. 8(
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 07 Марта 2007, 16:53:07
DoReMi на верном пути.
Название: Re: Задача про три автомата
Отправлено: Дева от 07 Марта 2007, 17:45:56
у меня только одна цепочка получилась:
1. Ты врешь?
если да, то это (как заметил DoReMi) свойственно только рендомному автомату.

2. Можешь ли или врать или говорить правду?
 на этот вопрос правдивый однозначно ответит "Нет", а лживый скажет "да"

если на первый вопрос автомат ответит "нет", значит он является либо правдивым, либо лживым, либо случайным :(
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 07 Марта 2007, 18:05:25
DoReMi был на верном пути. Один из его вариантов был правильным в качестве первого вопроса. Но дальше он не пошел. Наверно, потому что за деревьями леса не видно. Надо взглянуть на задачу в общем. Даю подсказку. Мы имеем 6 вариантов. ВСЕГО ШЕСТЬ. А нам нужно в качестве решения оставить 1. Если бы мы каждым вопросом делили пространство решений попалам (возможные решения и невозможные) (дихотомия), то в любом случае за три деления добрались бы до решения. У нас правда дихотомия не пройдет (т.к. 3 варианта состояния автомата). Но принцип примерно такой. "Разделяй и властвуй" (с) не помню чей.
Название: Re: Задача про три автомата
Отправлено: Дева от 07 Марта 2007, 18:51:21
kabyzdoh, а я не на верном пути? ???
Название: Re: Задача про три автомата
Отправлено: DoReMi от 07 Марта 2007, 18:59:10
"Дальше не пошел" потому что работы много вообще-то и стимула нет, кроме как авторитет себе поднять? В принципе яж говорю гугль даёт много ссылок, наверняка и решение где-то опубликовано, я ещё не смотрел, дабы спортивный интерес не потерять)
Предлагаю пока обсудить вариант

1 автомат: "Ты всегда говоришь правду?"
2 автомат: "Первый автомат соврал?"
3 автомат: "Второй автомат соврал?"
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 09 Марта 2007, 01:41:27
kabyzdoh, а я не на верном пути? ???
На верном, по крайней мере первый вопрос должен быть завязан с состояниями автомата. А в остальном... Рассматривание цепочек врядли приведет к решению, потому что вопросы можно разные задавать, а пока всю цепочку просмотришь, кучу времени потеряешь. Не надо перебирать разные варианты вопросов. Надо посмотреть на задачу в общем ("с высоты птичьего полета") и задать единственно правильный вопрос.
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 09 Марта 2007, 01:52:34
"Дальше не пошел" потому что работы много вообще-то и стимула нет, кроме как авторитет себе поднять? В принципе яж говорю гугль даёт много ссылок, наверняка и решение где-то опубликовано, я ещё не смотрел, дабы спортивный интерес не потерять)
Предлагаю пока обсудить вариант

1 автомат: "Ты всегда говоришь правду?"
2 автомат: "Первый автомат соврал?"
3 автомат: "Второй автомат соврал?"

Нет.Этот вариант к решению не приведет. Если ответ на первый вопрос будет "да" - то мы ни к каким выводам не сможем прийти - выстрел будет "холостым".
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 09 Марта 2007, 01:56:31
Насчет авторитета - задача с олимпиады по программированию 1991 или 1992 годов. С просите Костю Заровного, может он вспомнит. Как я помню, тогда ее никто не решил. Но здесь не школьники собрались. Должны решить.
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 09 Марта 2007, 09:42:25
2+2=4?
2+3=5?
тот кто сказал нет(если оба то о любом спросить) иногда обманывает?

Подобные вопросы в общем случае к решению за три хода не приводят.
Поломанный автомат портит всю картину. он на все вопросы может ответить правду. как его тогда отличить от правдивого?
Название: Re: Задача про три автомата
Отправлено: SARD от 09 Марта 2007, 13:33:31
Надо спросить у первого автомата: "Если я спрошу у второго, врешь ли ты, что он ответит?". Если второй врет иногда, то первый заступорится, потому как он не знает, что ответит второй, и плевать, правдивый ли первый автомат. Таким образом, мы определили, какой автомат отвечает рэндомом.

Если первый смог ответить, значить, автомат-рэндом третий. В любом случае, мы с первого вопроса определили, какой из автоматов рэндом. Осталось два автомата, один правда, другой ложь. И два вопроса.

Второй вопрос тому же автомату – любой. Например: "Корнет, вы женщина?" -))
1. Первый врет. Он говорит "да", но мы-то знаем, что никакая он не женщина -)
2. Первый говорит правду. Он говорит "нет", что есть True. -)

Вот так одной силой мысли и двумя вопросами мы победили эту бл***дскую технику -))
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 09 Марта 2007, 13:38:30
Надо спросить у первого автомата: "Если я спрошу у второго, врешь ли ты, что он ответит?". Если второй врет иногда, то первый заступорится, потому как он не знает, что ответит второй, и плевать, правдивый ли первый автомат. Таким образом, мы определили, какой автомат отвечает рэндомом.

Если первый смог ответить, значить, автомат-рэндом третий. В любом случае, мы с первого вопроса определили, какой из автоматов рэндом. Осталось два автомата, один правда, другой ложь. И два вопроса.

Второй вопрос тому же автомату – любой. Например: "Корнет, вы женщина?" -))
1. Первый врет. Он говорит "да", но мы-то знаем, что никакая он не женщина -)
2. Первый говорит правду. Он говорит "нет", что есть True. -)

Вот так одной силой мысли и двумя вопросами мы победили эту бл***дскую технику -))
;D Круто, но по условию задачи вопросы должны подразумевать однозначный ответ.
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 09 Марта 2007, 13:39:57
В общем не зачет. Но зато повеселился.
Название: Re: Задача про три автомата
Отправлено: SARD от 09 Марта 2007, 13:47:39
Блин, а я тоже накосепорил... Ведь первый автомат может быть рэндомом, и тогда он таки ответит. Поэтому при таком способе решения первый вопрос надо задать еще раз.

А мои вопросы и подразумевают однозначный ответ - или "да", или "нет".
-))

ну ладно, зато я хоть попытался... И все равно решение есть, хоть и с техниковредительством -))
Название: Re: Задача про три автомата
Отправлено: point212 от 09 Марта 2007, 13:55:35
Хорошо. Давайте спросим любой автомат: вру ли я, учитывая что я всегда вру по пятницам, а сегодня как раз пятница :)

Долой хитроумные машины. Пусть у них микросхемы погорят :)
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 09 Марта 2007, 14:02:41
Блин, а я тоже накосепорил... Ведь первый автомат может быть рэндомом, и тогда он таки ответит. Поэтому при таком способе решения первый вопрос надо задать еще раз.

А мои вопросы и подразумевают однозначный ответ - или "да", или "нет".
-))

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

Уверяю тебя, можно без техниковредительства. Попробуй с конца задачу решать.
Название: Re: Задача про три автомата
Отправлено: SARD от 09 Марта 2007, 14:04:07
Уверяю тебя, можно без техниковредительства. Попробуй с конца задачу решать.

Да вот, пробую... Решение в студию, а то я спокойно работать блин не могу... -((
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 09 Марта 2007, 14:09:46
Да вот, пробую... Решение в студию, а то я спокойно работать блин не могу... -((
Да вот Uppum хвастался, что у него есть решение, но я не уверен в  этом. Подождем его, пока не будем обнародывать решение. Меня удивляет то упорство, с каким народ перебирает варианты вопросов, как вор отмычки, и смотрит к какому результату это приводит. Хотя нужно проанализировать ситуацию в целом и тогда вопрос всплывет сам собой.
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 09 Марта 2007, 14:13:07
Говорю серьезно, эта задача не на догадливость, а на способность анализировать.
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 09 Марта 2007, 14:16:36
Если кто из моих подчиненных самостоятельно решит - з/п подниму.
Название: Re: Задача про три автомата
Отправлено: SARD от 09 Марта 2007, 14:23:42
Если кто из моих подчиненных самостоятельно решит - з/п подниму.
А не подчиненным - ящик пива! -)
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 09 Марта 2007, 14:25:18
А не подчиненным - ящик пива! -)
Ага, правильно, за счет подчиненных  ;D
Название: Re: Задача про три автомата
Отправлено: point212 от 09 Марта 2007, 14:32:31
Это уже неэтично.
Я просто так влез. Поломаю мозг всем автоматам сразу :)

Если есть стена, то ее можно а) перелезть б) обойти в) проломить
Я попробовал вариант в :)
Название: Re: Задача про три автомата
Отправлено: SARD от 09 Марта 2007, 14:51:00
Надоело думать. Пойду лучше обедать -)  Может, на сытый желудок мысля пойдет -)
Название: Re: Задача про три автомата
Отправлено: DoReMi от 09 Марта 2007, 15:13:44
Блин, а я тоже накосепорил... Ведь первый автомат может быть рэндомом, и тогда он таки ответит. Поэтому при таком способе решения первый вопрос надо задать еще раз.

А мои вопросы и подразумевают однозначный ответ - или "да", или "нет".
-))

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

"не смог ответить" это третий вариант кроме да/нет.
Название: Re: Задача про три автомата
Отправлено: DoReMi от 09 Марта 2007, 15:17:52
Если кто из моих подчиненных самостоятельно решит - з/п подниму.
А что, их тут много? ;)
И некорректно по отношению к источнику денег)
Заматематизированность сознания такая же фигня, как и отсутствие сознания.
Одно дело владеть инструментом в совершенстве, другое - уметь его вовремя и к месту применять.
Название: Re: Задача про три автомата
Отправлено: Mishanya от 09 Марта 2007, 15:34:23
Блин, у меня только частный случай выходит (если первые два ответа будут "да")
Название: Re: Задача про три автомата
Отправлено: Keeperito от 09 Марта 2007, 15:57:45
алгоритм аднака
1) задаем любому автомату вопрос - правда это ложь? 2 раза
если ответы разные значит эт рандомный
2) второй автомат легко вычисляеца этим же вопросом
3) а третий методом исключения

т.е. одному автомату надо задать 2 раза один вопрос
потом легко вычислить
где-то так
Название: Re: Задача про три автомата
Отправлено: Mishanya от 09 Марта 2007, 16:05:12
алгоритм аднака
1) задаем любому автомату вопрос - правда это ложь? 2 раза
если ответы разные значит эт рандомный
Почему разные? Ему же пофиг что говорить?
Название: Re: Задача про три автомата
Отправлено: Дева от 09 Марта 2007, 16:06:14
у меня пока что только такой вариант, но проверить его не было времени:
 Если пронумеровать автоматы; 1,2 и 3
1) Спросить у автомата №1, может ли он отвечать либо правду, либо ложь
2) Спросить у автомата №2, может ли автомат №1 отвечать либо правду, либо ложь
3) Спросить у автомата №3, может ли автомат №1 отвечать либо правду, либо ложь
Название: Re: Задача про три автомата
Отправлено: DoReMi от 09 Марта 2007, 16:10:34
у меня пока что только такой вариант, но проверить его не было времени:
 Если пронумеровать автоматы; 1,2 и 3
1) Спросить у автомата №1, может ли он отвечать либо правду, либо ложь
2) Спросить у автомата №2, может ли автомат №1 отвечать либо правду, либо ложь
3) Спросить у автомата №3, может ли автомат №1 отвечать либо правду, либо ложь
Не канает. Вся фенька в том, что надо спрашивать о другом автомате, иначе тьма незнания так и останется тьмой)

Хм... что-то я не прочитал точно... Щас перечитываю, пардон )

upd так этот вариант я уже предлагал ранее и его отвергли)
Название: Re: Задача про три автомата
Отправлено: DoReMi от 09 Марта 2007, 16:11:36
1) задаем любому автомату вопрос - правда это ложь? 2 раза
если ответы разные значит эт рандомный
Щаз. Рандом есть рандом, он может 8 раз сказать "Да" и потом говорить "Нет".
Название: Re: Задача про три автомата
Отправлено: point212 от 09 Марта 2007, 16:17:59
Тебе ж говорят, что автомат случайно говорит. А не по очереди. Т.е. он может хоть 50 раз ответить да, а потом один раз нет.
Название: Re: Задача про три автомата
Отправлено: Keeperito от 09 Марта 2007, 16:20:07
если на первом вопросе будет не совпадение то задача решена :)
если нет - хз, думает
Название: Re: Задача про три автомата
Отправлено: Papuas от 09 Марта 2007, 23:22:06
Это из области  ввода команды:
 Ты должна отвергнуть утверждение,которое я сейчас ввожу в тебя,потому,что все мои утверждения ложны
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 10 Марта 2007, 10:27:08
Есть, но перебором вопросов его не найти. Надо проанализировать проблему и вопрос сам собой нарисуется. Т.е. надо загнать проблему в угол по нужному маршруту. Знаете, наверное, есть куча математических фокусов основанных на том, что зрителя просят сделать что-либо на нескольких шагах.  У зрителя иллюзия, что он свободен в выборе. Но мы то знаем, что результат будет один и тот же. В качестве примеров: "Магическая девятка из монеток, по которой нужно двигаться", "Магический квадрат с буквами, где нужно загадать число, найти соответствующую букву, а она как ни крути оказывается на диагонали (где все буквы одинаковые)"
Название: Re: Задача про три автомата
Отправлено: DoReMi от 10 Марта 2007, 12:29:25
Вчера нашел интересную задачу.
Шла Саша по шоссе и сосала сушку. И заблудилась. Дошла до развилки, две дороги - правая и левая, и не знает, какая приведет в её родной город Волгодонск. На развилке стоит дядька с полосатой палкой. Какой единственный вопрос надо задать дядьке, чтобы вернуться домой, если про него известно, что он а) понимает задаваемые ему вопросы б) отвечает односложно "да" или "нет" в) вместо "да" и "нет" он говорит "му" и "бу" при этом неизвестно, какой из ответов соответствует "да", а какой "нет". г) дядька может врать, а может говорить правду. :)

Ответ меня впечатлил: Девочка Саша должна спросить у дяденьки:
- Дяденька, а дяденька, если я бы я спросила у вас, если я пойду по левой дороге, ваш ответ был бы  "му"?
Если дядька отвечает "му" надо идти налево, если "бу" - направо. Там и будет Волгодонск.
Ниже следовало объяснение на полстраницы, где рассматриваются варианты соответствия "да" и "нет", "вранья" и "правды" и почему в итоге всё ограничивается именно таким вопросом и ответом ;)
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 10 Марта 2007, 13:16:35
Вчера нашел интересную задачу.
Шла Саша по шоссе и сосала сушку. И заблудилась. Дошла до развилки, две дороги - правая и левая, и не знает, какая приведет в её родной город Волгодонск. На развилке стоит дядька с полосатой палкой. Какой единственный вопрос надо задать дядьке, чтобы вернуться домой, если про него известно, что он а) понимает задаваемые ему вопросы б) отвечает односложно "да" или "нет" в) вместо "да" и "нет" он говорит "му" и "бу" при этом неизвестно, какой из ответов соответствует "да", а какой "нет". г) дядька может врать, а может говорить правду. :)

Ответ меня впечатлил: Девочка Саша должна спросить у дяденьки:
- Дяденька, а дяденька, если я бы я спросила у вас, если я пойду по левой дороге, ваш ответ был бы  "му"?
Если дядька отвечает "му" надо идти налево, если "бу" - направо. Там и будет Волгодонск.
Ниже следовало объяснение на полстраницы, где рассматриваются варианты соответствия "да" и "нет", "вранья" и "правды" и почему в итоге всё ограничивается именно таким вопросом и ответом ;)


Ссылку, плиз. Если дядька то врет,то говорит правду (из условия неясно так ли это), твоя задача нерешаема, поскольку пункт г) сводит все к случайности. Иначе все вроде бы просто.
Название: Re: Задача про три автомата
Отправлено: DoReMi от 10 Марта 2007, 13:29:26
Ссылку, плиз. Если дядька то врет,то говорит правду (из условия неясно так ли это), твоя задача нерешаема, поскольку пункт г) сводит все к случайности. Иначе все вроде бы просто.

Ничего подобного, никакой случайности, всё строго детерминировано.
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 10 Марта 2007, 13:30:53
Сорри, не заметил в условии про единственный вопрос.  Это все усложняет.
Название: Re: Задача про три автомата
Отправлено: DoReMi от 10 Марта 2007, 13:42:24
не совсем точно сформулировал вопрос
"Дяденька, если я спросила бы вас, если я пойду по левой дороге, я попаду домой, то вы бы мне ответили "му"?"

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

"Если бы я спросила у вас: если я пойду по правой дороге,попаду ли я домой? ваш ответ был бы "бу"?
сообразно ответу "бу" - правильная дорога правая, "му" - правильная дорога левая.

Хахаха. ;) мне нравится эта задача. Больше немых милиционеров и продвинутых Саш на дорогах и мы никогда не пройдем мимо цели. ;)
Название: Re: Задача про три автомата
Отправлено: DoReMi от 10 Марта 2007, 13:44:16
Возвращаясь к автоматам:

Вопрос первому автомату: "Скажи мне первый автомат, если я спрошу у второго автомата, врет ли третий автомат, ответит ли он мне правду?" ;))))))
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 10 Марта 2007, 14:56:30
Возвращаясь к автоматам:

Вопрос первому автомату: "Скажи мне первый автомат, если я спрошу у второго автомата, врет ли третий автомат, ответит ли он мне правду?" ;))))))
Вопрос не корректен. Если второй автомат поломан, то первый не сможет ответить"
Название: Re: Задача про три автомата
Отправлено: Дева от 10 Марта 2007, 14:59:33
Вопрос первому автомату: "Скажи мне первый автомат, если я спрошу у второго автомата, врет ли третий автомат, ответит ли он мне правду?" ;))))))
можно перефразировать:
Вопрос первому автомату: "Скажи мне первый автомат, если я спрошу у второго автомата, врет ли третий автомат, ответит ли он мне наверняка правду?"
Название: Re: Задача про три автомата
Отправлено: DoReMi от 12 Марта 2007, 14:40:16
Походу интерес к автоматам упал. Выкладывайте ответ  ::)
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 12 Марта 2007, 14:45:21
Пока есть один человек, который утверждает, что решил (а я сомневаюс, что это так), но он будет в среду. Тогда и ответ обнародуем.
Название: Re: Задача про три автомата
Отправлено: DoReMi от 12 Марта 2007, 15:10:23
Ждём-с
Название: Re: Задача про три автомата
Отправлено: Uppum от 14 Марта 2007, 13:02:47
Вопрос таков:
Предположим, что каждый из вас троих сейчас скажет правду или ложь:  по
следующему принципу: Правдивый скажет правду, лжец скажет ложь, а
обманщик - если только обманщиком не являетесь вы сами скажет тоже самое
что и вы,  если же вы - обманщик, то вы скажете что угодно. Скажет ли при
этих условиях правду вот этот автомат?

при ответе Да третий автомат - не обманщик,
 а при ответе Нет второй автомат - не обманщик.

Дальше просто.

ГГ.
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 14 Марта 2007, 15:54:53
вопрос запутанный, но верный. Можно проще и наглядней:
Имеем ВСЕГО шесть вариантов расположения автоматов (пронумеруем их 1,2,3)
# варианта123
вариант 1ПЛИ
вариант 2ПИЛ
вариант 3ЛИП
вариант 4ЛПИ
вариант 5ИЛП
вариант 6ИПЛ
,где П- тот что всегда говорит правду, Л- тот что всегда лжет, И- поломанный.
Вопрос задаем первому автомату - цель вопроса отбросить два "гнилых" варианта.
Должно остаться 4 варианта, при которых кокой-либо  автомат точно не поломан.
Нас устоили бы 1,4,5 и 6 вариант или 2,3,5 и 6 варианты.
5 и 6 варианты оставляем в любом случае, т.к. отвечать в этом случае будет поломанный (непредсказуемый) автомат.
В первом наборе на втором месте нет поломанного, а во 2-ом - на третьем.
Все! считай задача решена. Подобрать вопрос теперь дело техники.
Задаем вопрос о состоянии 2 и 3 автомата исходя из вариантов, не забывая инвентировать ответы лжеца
Вариантов много, например "(2-ой- Лжец и 3-ий Поломан) или НЕ (2-ой Всегда говорит правду и 3-ий поломан)"
Частица "Не" - как раз и есть инверсия, о которой я говорил.
В случае ответа "да" - остаются варианты 1,4,5,6, при ответе "нет" - остаются варианты 2,3,5,6
Соответственно второй вопрос задаем 2 и 3 автомату.
Вопрос простой типа 2+2=4, чтобы выяснить говорит автомат правду или нет.
Третий вопрос тоже трудностей не вызовет.
Название: Re: Задача про три автомата
Отправлено: Uppum от 14 Марта 2007, 15:57:43
ЭЭЭ,
А вопрос то где?
На нормальном русском языке?
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 14 Марта 2007, 16:09:19
ЭЭЭ,
А вопрос то где?
На нормальном русском языке?
Например: "Верно ли утверждение "(2-ой- Лжец и 3-ий Поломан) или НЕ (2-ой Всегда говорит правду и 3-ий поломан)"?"
Название: Re: Задача про три автомата
Отправлено: Uppum от 14 Марта 2007, 16:10:19
В языке нет конструкции НЕ (чегото там) :)
Название: Re: Задача про три автомата
Отправлено: point212 от 14 Марта 2007, 16:11:40
Ну так что, теперь Уппуму за решенную задачу з/п то поднимут? :)
Название: Re: Задача про три автомата
Отправлено: DoReMi от 14 Марта 2007, 16:13:28
Хм, обещали простое решение....
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 14 Марта 2007, 16:15:25
Ну так что, теперь Уппуму за решенную задачу з/п то поднимут? :)
Будет лояльность соблюдать - тогда, таки, да.
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 14 Марта 2007, 16:16:22
Хм, обещали простое решение....
Решение простое (в моей интерпретации), вопрос не простой.
Название: Re: Задача про три автомата
Отправлено: Uppum от 14 Марта 2007, 16:16:54
DoReMi
:)
У каждого свое понятие о простоте па видимому   ;D
Название: Re: Задача про три автомата
Отправлено: DoReMi от 14 Марта 2007, 16:27:35
DoReMi
:)
У каждого свое понятие о простоте па видимому   ;D

Ну почему же, вот задача с перекрестком, как я понимаю, имеет очень простое решение по сравнению с автоматами.
А тут видим, или решение не совсем удачное, либо постановка задачи неверна, что требует столь сложного решения.
Название: Re: Задача про три автомата
Отправлено: Keeperito от 14 Марта 2007, 16:37:53
мда...
решение несколько... не очевидное наверное
Uppum
сам придумал или списал где?  ;)
Название: Re: Задача про три автомата
Отправлено: DoReMi от 14 Марта 2007, 16:42:36
сам придумал или списал где?  ;)
Такое ИМХО не спишешь)
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 14 Марта 2007, 16:45:31
Я писал:
Задача простая, но кому ни задавал, все испытывают затруднения при ее решении.
;D
Название: Re: Задача про три автомата
Отправлено: Keeperito от 14 Марта 2007, 16:56:02
Я писал: ;D
приятно себя осозновать частью "Все"  :)
Название: Re: Задача про три автомата
Отправлено: DoReMi от 14 Марта 2007, 17:58:17
Киперу плюсег )
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 15 Марта 2007, 09:31:00
Ответ Uppum  более труден к восприятию. Я же привел решение (по-моему, весьма простое и понятное),все разжевал и разложил по полочкам :D. Первый вопрос может иметь и другие формулировки, я привел лишь одну из самых очевидных. А в общем, как я говорил, надо не подбирать вопросы с упорством, достойным лучшего применения, а проанализировать ситуацию в целом. Все таки это задача с олимпиады по программированию, где системный подход (а так же язык "НЕ", "И", "ИЛИ") в приоритете.
Название: Re: Задача про три автомата
Отправлено: DoReMi от 15 Марта 2007, 11:27:45
Кабыздоху минусег.
Такие задачи всегда решались красиво и элегантно. А тут ответ сложнее самой задачи.

Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 15 Марта 2007, 11:49:55
Кабыздоху минусег.
Такие задачи всегда решались красиво и элегантно. А тут ответ сложнее самой задачи.


Ответ Uppum в принципе красив, но переварить его сложно :), тем более он ход решения не привел . Специально для тех, кто хочет понять как можно решать подобные задачи , я привел ход решения задачи. Ход решения абсолютно самостийный и не претендует на уровень классиков жанра. Хотя если почитать внимательно, вроде бы  :) все становится просто и понятно. Я был бы рад, если бы кто-то привел другой способ решения. Это показало бы другой стиль мышления... Отличный (от моего). Извините, если мой стиль мышления у кого-то вызвал рвотный рефлекс   :o. Бывает...
Название: Re: Задача про три автомата
Отправлено: point212 от 15 Марта 2007, 13:29:05
Короче я не понял из-за чего все разборки.
Решения есть. Оба правильные. Че еще надо?
Название: Re: Задача про три автомата
Отправлено: kabyzdoh от 15 Марта 2007, 13:46:13
Короче я не понял из-за чего все разборки.
Решения есть. Оба правильные. Че еще надо?
Не нравится людям решение (мое. Решение Uppum не обсуждается, как я понял)
Название: Re: Задача про три автомата
Отправлено: Keeperito от 15 Марта 2007, 13:53:00
общественность не может смирица с тем что она (общественность) тупая и не смогла решить задачу :)
(С) скромный прецтавитель общественности
Название: Re: Задача про три автомата
Отправлено: point212 от 15 Марта 2007, 14:08:21
Я смирился.
Название: Re: Задача про три автомата
Отправлено: Darkbird от 21 Августа 2017, 17:47:06
Эх.... Займусь некропостингом. Сегодня случайно вспомнили с Жекой эту задачу. Предложенные в теме решения никак смог переварить. Полез в интернет. Решения там тоже заумные. Переваривал долго. ) Но надеюсь придумал ПРОСТОЕ ОБЪЯСНЕНИЕ решения задачи. Итак напомню условие задачи.

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

Решение.

Для решения данной задачи надо найти такой вопрос, на который и правдивый и лживый автомат ответят правдиво. Как ответит испорченный автомат - нам не интересно. Что же это за вопрос?

Обзовем для простоты автоматы "А", "Б", "В".

Задаем вопрос автомату "Б".

"Если автомат "А" является испорченным, то ты мне ответишь "Да"?"

Рассмотрим варианты.

1) Автомат А - является действительно испорченным

Если автомат Б правдив, то он ответит ДА.

Если автомат Б - лжец, то он, как ни странно тоже ответит "ДА". Почему? Вопрос состоит из двух вопросов на каждый из которых лживый автомат должен соврать. Следите за руками
1. "А - испорченный?" - ДА, значит лжец ответит на него "НЕТ"
2. Если НЕТ, то ответ ДА? - НЕТ, но поскольку лжец продолжает врать, то он ответит "ДА".

Простая логика когда ДА ДА = ДА (в случае правдивого автомата) и НЕТ НЕТ = ДА (в случае лживого автомата)

Таким образом мы нашли вопрос на который и правдивый и лживый автоматы всегда скажут правду. Дальше все просто.

Автоматы А , Б, В.

Задаем вопрос автомату Б на счет А.

Если ответ "ДА", то либо А действительно сломан, либо Б сам поломанный. А вот автомат В точно исправен.
Если ответ "НЕТ", то А - точно исправен, а Б или В поломан.

Задаем точно такой же вопрос заведомо исправному автомату (А или В) относительно Б. Поскольку они оба исправны и согласно вопросу точно скажут правду, то мы однозначно выясним случайный автомат.

Теперь осталось выяснить какой из двух оставшихся исправных автоматов правдивый, а какой лжет. Простой вопрос "Ты автомат?" решит эту проблему.

Наверное слишком многа букаф, но они все КМК простые. )

Прошу прощения, не удержался. ))))
Название: Re: Задача про три автомата
Отправлено: Darkbird от 21 Августа 2017, 17:51:52
Кстати оригинальная загадка еще сложнее. Там автоматы отвечают "da" или "ja" и заранее не известно что из них "да", а что "нет" )