Просмотр полной версии : Задача №4
В парламенте некоторой страны две палаты, имеющие равное число депутатов.
В голосовании по важному вопросу приняли участие все депутаты, причем воздержавшихся не было.
Когда председатель сообщил, что решение принято с преимуществом в 23 голоса,
лидер оппозиции заявил, что результаты голосования сфальсифицированы.
Как это он понял ?
**Ответ в личку :)
В тюрьме содержится заключенный, и при нем два стражника. Один говорит только правду, а другой всегда лжет. Дежурят они посменно: сутки один, сутки — другой.
Если заключенный узнает, кто из них кто, он сможет счастливо избежать своей участи; в противном случае его казнят. Он может задавать каждому стражнику любые вопросы, требующие односложного ответа: да/нет, касающиеся только одного аспекта: узнавания врет этот стражник и его напарник или нет.
И он узнал!
Как ему удалось?
P.S.: Знаю, что задача известная, но уж слишком понравился рекурсивный метод её решения :)
ILS, будешь смеяться, среди 4-х РАЗНЫХ решений, поступивших мне в личку, ни одного правильного :)
Буду смеяться. Прислать правильное?
Девочка-припевочка решила задачу №4.
Керцер присоединился к Припевочке и Юджину.
Керцер присоединился к Припевочке и Юджину.
№4, №5 или обе?
№4, №5 или обе?
№4
Так же №4 решили: Merla,Fessaer, wolf-hound и Kinder.
№5 пока не решил никто. Возможно, проблема в формулировке.
девочка-припевочка
05.12.2007, 15:55
вот вот.... что поняли по аспекту: "что от нас хотят"
то и написали
я про номер 5
Возможно ещё, что найденное Аристой для 5 задачи решение не верно :) судя по тому, что она начала объяснять- так и есть, впрочем, пусть сперва объяснит. Однако я не увидел, чем моё решение не отвечает предложенному условию- и если остальные привели то же решение- то выводы нашей парикмахерши... пардон, цирюльника :) слегка поспешны.
Илс, во-первых, не буди во мне зверя. Хотя бы сегодня. Сам знаешь, почему. Во-вторых, звонить мне по среди рабочего дня, когда у меня работы не в проворот, и надеяться на членораздельное объяснение - верх глупости. В третьих, проверь личку, там ответ и математическое доказательство.
В тему:
http://imgs.xkcd.com/comics/labyrinth_puzzle.png
А здесь у нас стражи Лабиринта. Один всегда говорит правду, другой всегда лжет, а третий убивает тех, кто пристаёт к нему с заковыристыми вопросами.
(And the whole setup is just a trap to capture escaping logicians. None of the doors actually lead out.)
отсюда (http://xkcd.com/246/)
Анечка, солнце, я не ждал по телефону толковых разьяснений и не собирался будить в тебе зверя. Твой ответ верен практически таким же образом, что и мой, только твой запутанней. Так или иначе, если тебе кто-то ещё ответил, как я- они тоже правы.
Всё в порядке товарещи! все ответы на №4 всегда правда, а на №5 всегда лож...
я тормоз, господа!
Итак, апдейт: задачу номер 5 решили Мерлин, Илс и Юджин.
Извращенец пешил задачу #4, а Фесс наконец-то справился с задачей #5.
девочка-припевочка
05.12.2007, 23:33
так если уж ты тормоз :) переделай нисуах задачи :)
девочка-припевочка, нисуах абсолютно тот же, просто я зациклилась на математическом решении.
Arista, а мой вариант был неправильным?
Условие имеет некоторую свободу трактовки просто. А так решение стандартное. Ань, жду ответа на мою задачу wink
Zigmar, твой был тоже правильным :)
Fessaer, Погоди, боссы свалят...
Alex_R решил задачу №4 :)
Ответ на задачу No4:
Общее число депутатов в парламенте - четное (в обеих палатах равное число депутатов).
Следовательно, четно суммарное число депутатов, голосовавших за принятие решения и против.
Но при четной сумме двух величин четна и их разность.
Поэтому, преимущество в 23 голоса (т.е. разность между числом дкпутатов, голосующих за принятие решения, и числом депутатов, голосующих против) есть не что иное, как фальсификация (либо, что менее вероятно, ошибка при подсчете голосов).
Один из вариантов правильного ответа на задачу No5:
У любого из стражников нужно спросить:
Если бы я спросил позавчера "ты лжешь?", ты бы ответил "да"? (Или, как вариант: "нет"? Но это сейчас трогать не будем: здесь всё абсолютно аналогично)
И тот и другой будут вынуждены дать "честный" ответ, то есть, их ответ будет соответствовать действительности, и не только на позавчерашний день, но и на сегодняшний.
Рассмотрим обе возможности.
1. Если мы спрашиваем честного стражника, то на наш вопрос мы получили бы ответ "нет". Так он ответил бы позавчера, так он отвечает и сейчас.
То есть, если у нас есть функция F, которая выдает значение истинности высказывания, содержащегося в вопросе, то имеем (обозначим такую функцию для первого стражника через F1):
F1(x) = x (какова истинность высказывания, таково и значение функции).
Применяя ее дважды (один раз к "позавчерашнему вопросу", другой раз к данному на него ответу), получим:
F1(F1(x)) = x
2. Если мы спрашиваем лживого стражника, мы имеем следующую картину.
Если бы мы задали позавчера ему тот же вопрос, мы получили бы лживый ответ. Т.е. на вопрос "ты лжешь?" он (как и честный стражник) ответил бы "нет"! Значит, теперь (когда мы спрашиваем про позавчерашний ответ), ему надо соврать нам еще раз и изменить свой тогдашний ответ на противоположный. Т.е. он ответит нам "да"! (По известному логическому закону — отрицание лжи есть правда).
Для этого стражника функция F уже имеет другой вид (обозначим ее через F2).
Если мы для любого значения истинности х обозначим противоположное ему значение как -х, получим:
F2(x) = -x
Зато применяя эту функцию дважды, мы получим совсем другую картину:
F2(F2(x)) = (вместо F2(x) подставим ее значение: -х) = F2(-x) = (вспомним, что каждое значение меняется на противоположное) = x
То есть:
F2(F2(x)) = x
И в первом и во втором случаях получили чистую правду!
Arista, если бы ты писала программу, для решения данной задачи по предложенному пути, то компьютер бы подвис. Как и стражник, который обязан ВСЕ время давать лживый ответ. То есть дав тебе честный ответ, лживый стражник нарушает исходное условие, в котором он ВСЕГДА врет.
Arista, если бы ты писала программу, для решения данной задачи по предложенному пути, то компьютер бы подвис. Как и стражник, который обязан ВСЕ время давать лживый ответ. То есть дав тебе честный ответ, лживый стражник нарушает исходное условие, в котором он ВСЕГДА врет.
Вот-вот :)
Почему? Позавчера он бы соврал, сегодня врет снова, все впорядке.
sirUjin, неа. По условию, стражник должен ВСЕГДА давать ложный ответ. Если он даст ответ, который так или иначе будет правдой, это нарушает исходное условие. Комп зависнет. Грубо говоря, вариант решения предложенный Аристой нельзя назвать решением, так как оно приводит задачу в логический тупик.
А как насчёт просто спросить "Что скажет о тебе второй стражник?"?
Честный ответит что второй скажет про него что он врёт,в то время как врун ответит что второй скажет про него что он честен. Условие соблюдено,решение понятно. Аня,ты так и не ответила хотя я тебе это решение послал :\
Фесс, почему? Он ведь оба раза соврал, и ни разу не сказал правды?
Честно говоря сам задумался - А что помешает лживому стражнику реально точно так же ответить, что позавчера он тоже не лгал? И каким образом в таком случае, решение, предоставленное Асей, является решением?
Почему нельзя спросить "ты стражник?", лжец ответит "нет" а правдивый "да" :)
Потаму что на такой вопрос, он не просто скажет нет, он скажет "нет, я конь в пальто!", и иди разберись, он сказал это с сарказмом, имел это ввиду на самом деле, или просто отмазывался от правдивого ответа...
девочка-припевочка
10.12.2007, 09:31
а почему нельзя спросить: "Ты вчера охранял?"
лгун ответит -да
а правдивый- нет
А потому что нельзя такие вопросы задавать. :jester:
девочка-припевочка
10.12.2007, 13:52
хм... а значит "Ты лжёшь?" можно? :)
да - прочитай условие. Можно задавать вопросы касающиеся аспекта выяснения лжет стражник или его друг, или нет.
То есть "ты\он лжешь\лжет\лгал сегодня\вчера\позавчера?" примерно.
- Товарищ прапорщик, вы сможете посторожить одного приговорённого к смерти?
- Смогу.
- И вопросов этого умника не боитесь? Он товарищ хитрый и въедливые.
- Нет.
После дежурства.
- Ну что, вопросы были?
- Только один. этит умник спросил: "Ты вчера охранял?"
- И что вы ответили?
- Я ответил уклончиво: "Да пошел ты на х#й!"
и в чем был прикол вопроса?
Никто не подвис бы и ничего не нарушил бы. Касательно программы- ты о принципе МВМН слыхал? В аглицком варианте, кажись GIGO :). А стражник сообщил ту ложь, что действительна на тот момент.
Впрочем, мой вариант решения, я полагаю, проще: "Если я спрошу твоего напарника, правдив [лжёт] ли он, он ответит да [нет]?" Честный ответит да [нет], лжец- нет [да] соответственно.
ILS, твой вариант и есть ответ на задачу.
Тот же вариант, который дал я, когда до меня доперло наконец, что от меня хотят.
"Та ложь, которая действительна на данный момент" это дополнительное условие, которое вносишь уже ты.:crazy girl: То есть ты решаешь несколько другую задачу.
-Доктор,меня все игнорируют!
-Следующий!
Я тот же ответ предложил,доброе утро...
Дык никто же не спорит, Жень.:crazy girl:
Во-первых, виноват, зевнул страничку 4, трудно читать тёмный шрифт на тёмном фоне. Во-вторых, любое высказывание может становиться либо правдой, либо ложью в зависимости от обстоятельств. И в-третьих, семантически в Анином варианте всё верно, т.к. охранник отвечает ложно на поставленный перед ним вопрос, а говорить правду "я тогда сказал бы нет" он не может по условию. Зато свойство этого вопроса таково, что лживый ответ на него является правдивым для подразумеваемого позавчерашнего "ты лжёшь?", при том, что сам он мог даже не задаваться, и охранник поэтому на него не отвечал.
И, кстати, поэтому парадокс лжеца тут не при чём. А предложенный большинством ответ верен в той же степени- зато проще :)
ILS, я думаю, что умный стражник найдет как нае...ть. :crazy girl:
И где евто ты видел умных стражников?
А ты думаешь, что хитросделанных заключенных охранять ставят дураков что ли? :girl_hospital:
Почему нет? Им интеллека не надобно. Им только распоряжения выполнять
Русский vBulletin v4.1.9, Copyright ©2000-2024, Jelsoft Enterprises Ltd. Перевод сделал zCarot