логическая задачка
Apr. 26th, 2004 03:09 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaБулос (Boolos) предлагает следующую задачку в качестве “The Hardest Logical Puzzle Ever”. Это, на мой взгляд, несколько преувеличено, но задачка действительно очень непростая. Придумал её Смаллиан (Smullyan) , а ещё более усложнил Джон Маккарти (John McCarthy, который изобретатель компьютерного языка Лисп).
Условие:
Вашу незначительную персону почтили своим присутствием трое богов. Их зовут True, False и Random. Бог по имени True всегда говорит правду, бог по имени False всегда лжёт, а бог по имени Random отвечает на все вопросы совершенно случайным образом.
К сожалению, вы не знаете, кто из них кто. Обозначим троих богов буквами A, B и C. Вы не знаете, кто из A, B и C на самом деле True, кто False, а кто Random. Сами боги это знают (о себе и других).
У вас есть возможность задать им три вопроса, на каждый из которых можно ответить только “да” или “нет”. Необязательно задавать каждому богу по одному вопросу; вы можете, если вам хочется, задать все три вопроса одному и тому же богу, или ещё как-нибудь. Вопросы задаются по порядку, то есть, например, в зависимости от ответа на первый вопрос вы можете выбрать, кому задавать второй вопрос и каким он будет.
Боги понимают ваш язык и ваши вопросы, но отвечают всегда на своём языке. В этом языке вместо “да” и “нет” говорят “oui” и “ja”. К сожалению, вы не знаете, что из них означает что — может быть, “oui” это “да”, а “ja” — “нет”, а может и наоборот.
Ваша задача: с помощью этих трёх вопросов точно определить, кто из них кто.
Условие:
Вашу незначительную персону почтили своим присутствием трое богов. Их зовут True, False и Random. Бог по имени True всегда говорит правду, бог по имени False всегда лжёт, а бог по имени Random отвечает на все вопросы совершенно случайным образом.
К сожалению, вы не знаете, кто из них кто. Обозначим троих богов буквами A, B и C. Вы не знаете, кто из A, B и C на самом деле True, кто False, а кто Random. Сами боги это знают (о себе и других).
У вас есть возможность задать им три вопроса, на каждый из которых можно ответить только “да” или “нет”. Необязательно задавать каждому богу по одному вопросу; вы можете, если вам хочется, задать все три вопроса одному и тому же богу, или ещё как-нибудь. Вопросы задаются по порядку, то есть, например, в зависимости от ответа на первый вопрос вы можете выбрать, кому задавать второй вопрос и каким он будет.
Боги понимают ваш язык и ваши вопросы, но отвечают всегда на своём языке. В этом языке вместо “да” и “нет” говорят “oui” и “ja”. К сожалению, вы не знаете, что из них означает что — может быть, “oui” это “да”, а “ja” — “нет”, а может и наоборот.
Ваша задача: с помощью этих трёх вопросов точно определить, кто из них кто.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2004-04-26 05:23 am (UTC)Зачем же звать его Смульяном.
no subject
Date: 2004-04-26 05:29 am (UTC)no subject
It was "da" and "ja" in the original article.
no subject
Date: 2004-04-26 05:45 am (UTC)no subject
Date: 2004-04-26 05:46 am (UTC)no subject
Date: 2004-04-26 05:49 am (UTC)no subject
Date: 2004-04-26 05:51 am (UTC)no subject
Date: 2004-04-26 05:52 am (UTC)no subject
Date: 2004-04-26 05:56 am (UTC)no subject
Date: 2004-04-26 05:56 am (UTC)no subject
Date: 2004-04-26 05:59 am (UTC)no subject
Date: 2004-04-26 05:59 am (UTC)no subject
Date: 2004-04-26 06:20 am (UTC)Ответы Random могут в точности совпадать с ответами True и False, так что даже если вычислить False или True (вопросами типа 2+2=4?), то затем отличить Random от оставшегося бога невозможно.
Любопытно посмотреть на правильные вопросы.
no subject
Date: 2004-04-26 06:23 am (UTC)no subject
Date: 2004-04-26 06:24 am (UTC)no subject
Date: 2004-04-26 06:27 am (UTC)no subject
Date: 2004-04-26 06:29 am (UTC)no subject
Date: 2004-04-26 06:30 am (UTC)no subject
Date: 2004-04-26 06:36 am (UTC)no subject
Date: 2004-04-26 06:44 am (UTC)Я бы даже задачу сформулировал так...
Два бога, один (да хоть сотня) из которых отвечает на вопросы правдиво (Good), а другой отвечает случайным образом (Bad). Задать любое количество вопросов таким образом, чтобы найти, кто из A и B является Good, а кто Bad.
Любопытность в том, что при "плохом" стечении случайностей наборы вопрос-ответ для обоих богов окажутся одинаковыми.
А в сети есть сборники "правильных" (я-то их правильными не считаю :)) вопросов?
no subject
Date: 2004-04-26 06:46 am (UTC)http://www.livejournal.com/users/avva/1171209.html?thread=19122697#t19122697
no subject
Date: 2004-04-26 06:46 am (UTC)Easy way out: Спросить про ответ Рэндома - если не отвечает - значит не рэндом. задача сводится к Смаллиновскому оригиналу...:)
no subject
Date: 2004-04-26 06:49 am (UTC)Не найти её, прикинув для себя решение я не смог, поэтому сюда его уже писать не буду (тем более, в нём была небольшая ошибка). Но задачка -- просто великолепная. Много хорошего настроения:) Спасибо!
no subject
Date: 2004-04-26 06:53 am (UTC)no subject
Date: 2004-04-26 06:57 am (UTC)