логическая задачка
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:46 am (UTC)no subject
Date: 2004-04-26 05:51 am (UTC)no subject
Date: 2004-04-26 07:55 am (UTC)Есть 3! = 6 разных комбинаций (вариантов кто есть кто), из которых надо найти 1.
Дано 3 вопроса, что соответственно 2^3 = 8 комбинаций ответов. Значит в принципе можно сделать покрытие из 8 в 6.
Но это значит что выяснить что такое "да" и что такое "нет" не удасться (да и не требуется) т.к. это уже требует из 8 последовательностей ответов найти одну из 2*3!=12 комбинаций
no subject
Date: 2004-04-26 09:44 am (UTC)