?

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 ]

логическая задачка [сент. 2, 2001|03:00 am]
Anatoly Vorobey
[Настроение |nerdynerdy]

В детстве, помню, буквально глотал всякие сборники логических задачек. Все, наверное, помнят такой целый класс задач о лжецах и правдивых людях: например, путник, встречая на перекрёстке человека, который либо всегда врёт, либо всегда говорит правду, должен выяснить одним вопросом, по какой дороге ему надо идти дальше.

А вот пару дней назад случайно наткнулся на задачку с похожим условием, но более тяжёлую, чем обычно для таких задачек. Мне её понравилось решать. Если кому интересно - попробуйте свои силы:

На некотором острове живут: люди, которые всегда говорят правду, люди, которые всегда лгут, и люди, которые просто отвечают наугад, случайным образом. Причём они всегда ходят по три человека, так, что в каждой тройке есть по одному представителю каждого типа. Путник встретил такую тройку. Может ли он определить, кто есть кто, задав всего три двоичных вопроса (т.е. вопроса, на каждый из которых существуют всего два ответа)? Каждый вопрос можно задавать только одному человеку. Жители острова знают друг о друге и о себе самих, кто есть кто.
СсылкаОтветить

Comments:
[User Picture]From: french_man
2001-09-01 05:30 pm

Опять

провоцируете? Но я Вам отомщу.

В свое время в "Кванте" была следующая великая задача.

N участников некого конгресса делятся на химиков и алхимиков, причем химиков больше. Химики всегда говорят правду, а алхимики иногда правдивы, а иногда лгут. Определить, кто есть кто, задав 2N–2 вопроса.

Я до сих пор больше горжусь решением этой задачи, чем многими из своих оригинальных результатов. Это притом, что 2N–2 можно улучшить. Впоследствии в "Кванте" была статья, показывающая, что 3N/2 (или вроде того) достаточно, а меньше недостаточно.
(Ответить) (Thread)
[User Picture]From: oxfv
2001-09-01 06:20 pm

Re: Опять

Действительно, эта посложнее будет. Аввину вроде решил (не скажу как, но ответ - конечно же, трех вопросов хватит), а с этой трудно...
(Ответить) (Parent) (Thread)
[User Picture]From: french_man
2001-09-01 09:32 pm

Дать подсказку?
(Ответить) (Parent) (Thread)
[User Picture]From: oxfv
2001-09-02 01:53 am
Дать, пожалуй. С трудом шестеренки шевелятся, рассуждения все какие-то на пальцах, бестолковые.
(Ответить) (Parent) (Thread)
[User Picture]From: french_man
2001-09-02 02:39 am

Пусть N четно. Разобьем всех на пары, и в каждой паре спросим у каждого о напарнике. Всего N вопросов.

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

Пусть М число химпар. Возьмем в каждой химпаре по представителю, получим множество из М участников, в котором химиков больше. По индукции, мы можем расколоть его за 2М–2 вопроса. Теперь мы знаем все о попавших в химпары. Об оставшихся N–2М можно спросить у любого известного химика, еще N–2М вопросов. Итого

N+2М–2+N–2М = 2N–2

вопроса.

Если N нечетно, то дело чуть сложнее. Чтобы разделить на пары, надо одного выбросить. В итоги, среди М химпар число пар химиков и пар алхимиков может сравняться. Но химиков не может стать меньше.

Если М нечетно, то химиков среди М представителей больше, и применяем предыдущее рассуждение. Если М четно, то делим их на пары опять, и т.д. Этот процесс продолжаем до одной из следующих ситуаций:

(а) на каком–то шаге число химпар оказалось нечетным. Тогда индукция, с подсчетом числа вопросов как в первом случае, но чуть более сложным.

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

Привет,

Французик.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2001-09-02 02:34 am

Re: Опять

Хммммм.
А вопросы только да-нет или можно попросить, например, показать на алхимика? А участники конгресса все знают, кто есть кто?
(Ответить) (Parent) (Thread)
[User Picture]From: french_man
2001-09-02 02:45 am

pardon

я ее нечаянно решил. Хотел Валере чуть подсказать, а вместо этого написал решение. Пакость не получилась. Отложим на потом.

Вопросы двоичные. Должны знать кто есть кто. Без этого, кажется, даже троих нельзя вычислить за конечное число вопросов.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2001-09-02 02:50 am

Re: pardon

Я ещё не прочитал решение, отшатнулся в ужасе, когда письмо открыл. Так что может ещё подумаю, если невтерпёж не пересилит.
О! Фразой про конечное число вопросов Вы напомнили мне замечательную и малоизвестную задачку про математиков в тюрьме. Вот я сейчас Вам и отомщу.
(Ответить) (Parent) (Thread)
[User Picture]From: french_man
2001-09-02 01:09 am

А сами

жители знают, кто есть кто?
(Ответить) (Thread)
[User Picture]From: avva
2001-09-02 02:28 am

Re: А сами

Ага, знают. Исправил запись, спасибо.
(Ответить) (Parent) (Thread)
[User Picture]From: french_man
2001-09-02 02:50 am

тогда легко

Назовем их правдивыми, лжецами и идиотами.

Вопрос к 1–му: что ответит представитель твоей группы на вопрос, является ли 2–й идиотом?

Дальше ясно.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2001-09-02 02:55 am

Re: тогда легко

Неясно. Положим, первый - идиот. Он отвечает да или нет случайно на этот вопрос. Дальше что?
Вообще никакой информации не добавилось, т.к. и правдивый, и лжец тоже могли ответить и да, и нет.
(Ответить) (Parent) (Thread)
[User Picture]From: french_man
2001-09-02 03:12 am

Re: тогда легко

Если ответ "да", то либо первый идиот, либо второй идиот. Третий в любом случае не идиот. Если ответ "нет", то второй заведомо не идиот. Так или иначе, мы знаем про кого–то, что он не идиот. Этого достаточно, чтобы закрыться за два вопроса.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2001-09-02 03:17 am

Re: тогда легко

Да, логично. Не осознал сразу ;)
Известное мне решение работает на том же принципе, т.е. первым вопросом выделяем кого-то, кто не идиот, но не пользуется трюком косвенной ссылки, чтобы объединить лжеца с правдивым. Первый вопрос такой: Покажи мне того из двух других, кто следующий после тебя по "хужести" (считая, что лжец хуже правдивого, а идиот хуже лжеца).
(Ответить) (Parent) (Thread)
[User Picture]From: oxfv
2001-09-02 12:06 pm

Re: тогда легко

Если ответ "да", то третий-таки может быть идиотом - если первый - лжец, а второй - честняга-парень. Так что - не работает.

Я заодно понял, что мое решение тоже липовое. Пожалуй, аввино правильное и есть.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2001-09-02 12:24 pm

Re: тогда легко

Тут работает косвенная ссылка, обратите внимание на точную форму вопроса. Лжец знает, что человек его типа, т.е. лжец, на такой ответ ответит "да"; но он должен солгать и потому отвечает "нет".
(Ответить) (Parent) (Thread)
[User Picture]From: oxfv
2001-09-02 02:56 pm

Re: тогда легко

Шит, какие хытрые!
(Ответить) (Parent) (Thread)
[User Picture]From: french_man
2001-09-02 06:40 pm

Такие мы

французики!
(Ответить) (Parent) (Thread)
[User Picture]From: french_man
2001-09-02 12:40 pm

Нет, работает

Хотел сам написать, но Анатолий уже ответил.
(Ответить) (Parent) (Thread)
[User Picture]From: stas
2001-09-02 01:39 am
У Смаллиана есть цикл книжек, посвященных этому вопросу. У него там есть формула вопроса, который позволяет выяснить любой факт у любого из таких жителей. Вообще у него там весьма сильная теория на этот счет. Жалко, я эти книжки в Киеве оставил...
(Ответить) (Thread)
[User Picture]From: french_man
2001-09-02 02:16 am

смаллиан

Читал я эти книжки. Нудные до ужаса. Вампиры все какие–то.
(Ответить) (Parent) (Thread)
[User Picture]From: stas
2001-09-02 02:31 am

Re: смаллиан

Вампиры только в одной. Еще в одной принцессы и тигры, в одной взломы сейфов и еще в одной про Геделя. Их у меня 3 или 4 всего было, в каждой несколько частей. Мне очень нравилось :)
(Ответить) (Parent) (Thread)
[User Picture]From: french_man
2001-09-02 02:47 am

Re: смаллиан

Дело вкуса. Мне тоже друг порекомендовал с восторгом. А я предпочитаю нормальный "скучный" учебник логики.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2001-09-02 12:18 pm
помогите-спасите, все равно спорим и не можем разгадать :(((
(Ответить) (Thread)
[User Picture]From: avva
2001-09-02 12:27 pm
Первый вопрос человеку номер 1 такой: Покажи мне того из двух других, кто следующий после тебя по "хужести" (считая, что лжец хуже правдивого, а идиот хуже лжеца).

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

Вторым вопросом мы спрашиваем этого человека (на которого указали): "Умеешь ли ты разговаривать?". По его ответу мы понимаем, правдивый он или лжец. Третьим вопрос ему же: "Кто из двоих оставшихся идиот?" По его ответу, зная уже, правдивый он или лжец, мы определяем тип оставшихся двух людей.
(Ответить) (Parent) (Thread)
[User Picture]From: snyders
2001-09-02 01:11 pm

Thanks for a good puzzle.

>(считая, что лжец хуже правдивого, а идиот хуже лжеца).

pravdiviy -- huzhe idiota, t.k. inache nedoopredeleno, a idiotu vse ravno kak otvechat'.

>"Умеешь ли ты разговаривать?"

hmm.. smth fishy here (ambiguous question which may have no "Y/N" answer). What if their only knowledge in life is "who is who"?
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2001-09-02 02:23 pm

Re: Thanks for a good puzzle.

hmm.. smth fishy here (ambiguous question which may have no "Y/N" answer). What if their only knowledge in life is "who is who"?

That's an unreasonable restriction. Anyway, in that case ask him "are you an idiot?" (here ambiguous, but only because french_man suggested the ambiguous term "idiot" ;)).


(Ответить) (Parent) (Thread)