Здравствуйте, Pushkin, Вы писали:

P>Фразу "Дипломат отвечает случайным образом" можно понимать двояко.
P>- Он случайным образом выбирает ответ Да/Нет.
P>- Он случайным образом выбирает Соврать/Не соврать.
P>Во втором случае можно так поставить вопрос,
P>что при любом решении дипломат ответит Да.
P>Например, "Ты сейчас скажешь правду?".
P>Тогда можно предложить другое решение

Этот вопрос вышибет его за пределы исчисления высказываний, в пространство, где царит теорема Геделя
Вот такое сатори.

Можно еще спросить: "Ты сейчас солжешь?"

Или еще круче: "Твой ответ будет 'НЕТ'?"

Здравствуйте, Кодт, Вы писали:

К>Или еще круче: "Твой ответ будет 'НЕТ'?"

А еще можно спросить, принадлежит ли множество всех подмножеств некоторого счетного множества самому себе?

Здравствуйте, gloomy rocker, Вы писали:

GR>Здравствуйте, Кодт, Вы писали:

К>>Или еще круче: "Твой ответ будет 'НЕТ'?"

GR>А еще можно спросить, принадлежит ли множество всех подмножеств некоторого счетного множества самому себе?

Во-первых, простая проверка типов дает ответ "нет", неважно, счетное множество или какое другое.
Множество не есть свой элемент.

Можно говорить о мощности (размере) множества <=> эквивалентности множеств.

По определению, мощность множества всех подмножеств некоторого множества больше мощности исходного множества. Для бесконечных множеств возникает ряд "кардинальных чисел", называемый еще иерархией алефов.
Алеф-0 — мощность счетного множества,
Алеф-1 — мощность континуума (эквивалентного множеству подмножеств счетного множества)
Алеф-2 — мощность множества функций непрерывного аргумента
и т.д.
Алеф[N+1] = 2^(Алеф[N]) -- как бы

Функция f:X->Y есть некоторое подмножество множества X*Y; мощность функции-как-множества равна мощности области определения X.
Поэтому мощность всех возможных функций F { f:X->Y } есть кардинальное число следующего порядка,
||F|| = 2^||X||

В том числе поэтому функция (предикат), аргументом которого является функция, не может быть своим аргументом.

И хотя выразительность языка позволяет давать такие "парадоксальные" определения, толку от них мало
(Гедель не спал!)
Как говорил Ильич: "Один маленький лысый негодяй может такое спросить, что сто муд рецов не ответят".

Здравствуйте, Кодт, Вы писали:

К>Можно еще спросить: "Ты сейчас солжешь?"

все ответят Нет

К>Или еще круче: "Твой ответ будет 'НЕТ'?"

а вот этот вопрос даст лжецу возможность ответить по-любому, а рыцаря завесит на хрен, поэтому недопустим — нельзя задавать вопросы, на которые кто-то не сможет ответить не изменив своим принципам

Здравствуйте, Кодт, Вы писали:

GR>>А еще можно спросить, принадлежит ли множество всех подмножеств некоторого счетного множества самому себе?

Не подменяйте, речь не идёт о неразрешимых парадоксах.
"Ты сейчас ответишь правду" — нормальный, отвечаемый вопрос!
Просто на него и лжец и рыцарь отвечает одинаково, в этом его особенность.
"Ты сейчас ответишшь Да" и "Ты сейчас ответишь Нет" — парадоксальные вопросы —
они завешивают либо одного либо другого.

К>Во-первых, простая проверка типов дает ответ "нет", неважно, счетное множество или какое другое.

...и на этом можно поставить точку, дальнейшие разговоры о мощности не нужны (хоть и интересны)

К>Алеф-0 — мощность счетного множества,
К>Алеф-1 — мощность континуума (эквивалентного множеству подмножеств счетного множества)
К>Алеф-2 — мощность множества функций непрерывного аргумента

Раз ты такой спец, два вопроса меня всегда мучали:
1) как по-простому показать, что 2) мощнее 1) а 3) мощнее 2 ?
2) есть ли Алеф-1.5 ?

К>Как говорил Ильич: "Один маленький лысый негодяй может такое спросить, что сто муд рецов не ответят".

не поооонял, это кто?

Медитируя над верным, но сложным решением автора (с таблицами),
неожиданно нашёл эквивалентное, но совсем простое решение,
которое можно устно объяснить 10-летнему ребёнку за 5 минут (засекал ).

Основная фишка — спрашивать кого-нибудь, кто из двух оставшихся лживее.
— мера лживости понятна — лжец лживей дипломата, дипломат лживей рыцаря.
— чтобы удовлетворить условиям, вопрос будем формулировать "левый лживее?",
но рассуждать удобней именно с формулировкой "КТО лживее?".

Итак:
Спрашиваем первого, кто из оставшихся лживее.
Утверждение: тот, на кого укажут, НЕ дипломат:
если мы спрашивали рыцаря, он указал на лжеца,
если лжеца, он указал на рыцаря,
если дипломата, то среди тех двоих нет дипломатов.

У того, на кого указали, спрашиваем то же самое.
Таким образом находим, кто из оставшихся двоих НЕ дипломат.
Значит нашли дипломата.

Спрашиваем у любого НЕ дипломата, указывая на дипломата, "он дипломат?".
И окончательно узнаём кто есть кто.

Задача гениальная спасибо автору, я давно слышал, но обрывки.

Здравствуйте, Pushkin, Вы писали:

P>Основная фишка — спрашивать кого-нибудь, кто из двух оставшихся лживее.
Все правильно, вот только первым эту фишку просек Atilla. Я копался в его проге, и эта идея там присутствует.

P>- мера лживости понятна — лжец лживей дипломата, дипломат лживей рыцаря.
Собственно мера в упомянутом исходнике была задана куском кода:
const int liar=-1, crafty=0, honest=+1;

P>- чтобы удовлетворить условиям, вопрос будем формулировать "левый лживее?"
А это соответствует куску кода
if(ASK(0, a[1]>a[2]))// #1
j=2, k=1;
else
j=1, k=2;

P>Задача гениальная спасибо автору, я давно слышал, но обрывки.
Пожалуйста. Рад стараться, только я не совсем автор. Мне эту задачу рассказали, еще когда я учился в школе и занимался в математическом кружке. Тогда я ее решить не смог, а вот недавно вспомнил и решил.

Здравствуйте, gloomy rocker, Вы писали:

GR>Все правильно, вот только первым эту фишку просек Atilla. Я копался в его проге, и эта идея там присутствует.

Угу, кстати до этой идеи я дошел с помощью таблички. Получалось, что если 1-й вопрос считать функцией 2-х переменных, то она должна выглядеть так:

f(0, -1)=true    - правдивый скажет true
f(-1, 0)=false   - правдивый скажет false
f(0, +1)=false   - врун скажет true
f(+1, 0)=true    - врун скажет false

ну и что это за функция становится очевидно. Можно, конечно, записать (x==0 && y==-1) || (x==+1 && y==0), а можно проще: x>y.

GR>Пожалуйста. Рад стараться, только я не совсем автор. Мне эту задачу рассказали, еще когда я учился в школе и занимался в математическом кружке. Тогда я ее решить не смог, а вот недавно вспомнил и решил.

Я в детстве встречал (и решил) задачу про 3-х оракулов. Им можно было задавать любые вопросы (не только булевые ) и вопросы были известны. Т.е. задача была намного проще.

Здравствуйте, gloomy rocker, Вы писали:

P>>Основная фишка — спрашивать кого-нибудь, кто из двух оставшихся лживее.
GR>Все правильно, вот только первым эту фишку просек Atilla. Я копался в его проге, и эта идея там присутствует.

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

задача сформулирована в общечеловеческих терминах
и решение лучше формулировать в них же
так её легче запомнишь и большему числу людей объяснишь
у меня — полстраницы очень понятного русского текста
у Atilla — две страницы на Си, что лучше как итоговый результат?
это не умаляет ценности работы последнего
какой-то известный математик сказал именно об этом:
"вклад учёного в науку определяется количеством написанных им громоздких работ"

кстати у Atilla него чуть иначе
A>идея такая: первым вопросом определяем, какой автомат точно не является случайным. Вторым определяем, какой это именно автомат: врущий или правдивый.
а у меня мы до упора ищем мерзавца-дипломата, задавая всё тот же вопрос — опять же, так запомнить легче

P>>Задача гениальная спасибо автору, я давно слышал, но обрывки.
GR>Пожалуйста. Рад стараться, только я не совсем автор. Мне эту задачу рассказали, еще когда я учился в школе и занимался в математическом кружке. Тогда я ее решить не смог, а вот недавно вспомнил и решил.

Да не скромничай ты Для меня ты автор — без тебя я бы её ещё сто лет не знал.
А придумать такую задачу — это вообще можно сразу в гроб ложиться — жизнь не зря прожил

Здравствуйте, Atilla, Вы писали:

A>Угу, кстати до этой идеи я дошел с помощью таблички. Получалось, что если 1-й вопрос считать функцией 2-х переменных, то она должна выглядеть так:

A>

A>f(0, -1)=true    - правдивый скажет true
A>f(-1, 0)=false   - правдивый скажет false
A>f(0, +1)=false   - врун скажет true
A>f(+1, 0)=true    - врун скажет false
A>

A>ну и что это за функция становится очевидно. Можно, конечно, записать (x==0 && y==-1) || (x==+1 && y==0), а можно проще: x>y.

В моем решении базой была Булева алгебра, поэтому такое громоздкое выражение. Кроме того есть общее правило составления функций N булевых переменных, если известна таблица истинности. Этим правилом я и востпользовался. К стати, можно даже придумать электрическую схему на элементах И,ИЛИ,НЕ, которая будет решать эту задачу

Здравствуйте, Pushkin, Вы писали:


P>Основная фишка — спрашивать кого-нибудь, кто из двух оставшихся лживее.
P>- мера лживости понятна — лжец лживей дипломата, дипломат лживей рыцаря.
P>- чтобы удовлетворить условиям, вопрос будем формулировать "левый лживее?",
P>но рассуждать удобней именно с формулировкой "КТО лживее?".

Это конечно все хорошо, все правильно, но вот меня чего-то терзают смутные сомнения, ибо вы заранее полагаете, что "лжец лживей дипломата, дипломат лживей рыцаря". С точки зрения математики "лжец лживее либо одинаковой степени лживосит с дипломатом, а дипломат лживее либо одинаковой степени лживости с рыцарем", да и вообще можно ли так утверждать? Ведь из условия задачи вообще не известно ничего о существовании данной операции сравнения на данном множестве! По сему решение не совсем корректно, точнее задаваемый вопрос: "Кто из 2-ух оставшихся лживее?" не совсем удачен, а скорее не допустим. Лучше задавать более простой вопрос: "Среди 2-ух оставшихся нет "дипломата"?" и т.п.

Здравствуйте, Slaveniya, Вы писали:

S>Здравствуйте, Pushkin, Вы писали:

S>Это конечно все хорошо, все правильно, но вот меня чего-то терзают смутные сомнения, ибо вы заранее полагаете, что "лжец лживей дипломата, дипломат лживей рыцаря". С точки зрения математики "лжец лживее либо одинаковой степени лживосит с дипломатом, а дипломат лживее либо одинаковой степени лживости с рыцарем", да и вообще можно ли так утверждать? Ведь из условия задачи вообще не известно ничего о существовании данной операции сравнения на данном множестве! По сему решение не совсем корректно, точнее задаваемый вопрос: "Кто из 2-ух оставшихся лживее?" не совсем удачен, а скорее не допустим. Лучше задавать более простой вопрос: "Среди 2-ух оставшихся нет "дипломата"?" и т.п.

С этим вопросом я не знаю, как решать, это существенно другой вопрос.

По поводу "Кто лживее" могу переформулировать так:
"Верно ли, что задав вопрос человеку стоящему справа мы имеем больше шанс услышать правдивый ответ, чем если зададим тот же вопрос человеку стоящему слева". Так как дипломат иногда отвечает правдиво, а иногда лжёт (есть свидетели и того и другого), то всё нормально.

Если же и такая формулировка вопроса кажется вам сомнительной, ок — пусть у них у них будут имена Лжец, Рыцарь, Дипломат и спросите "Верно ли, что вторая буква в имени правого стоит правее в алфавите, чем вторая буква в имени левого"

Здравствуйте, gloomy rocker, Вы писали:

GR>Есть три автомата, которые умеют отвечать на любой вопрос, на который можно ответить "Да" или "Нет". Естественно все множество возможных ответов исчерпывается двумя вариантами: "Да", "Нет". Один из них всегда говорит правду, один всегда лжет, а оставшийся отвечает произвольным образом. Необходимо задать 3 вопроса и выяснить, кто есть кто.

Я посмотрел различные ответы, но не понимаю, как их авторы хотели выявить "Произвольного" на основании его "произвольных" ответов ?

Спрашиваем первого, кто из оставшихся лживее.
Утверждение: тот, на кого укажут, НЕ дипломат:
если мы спрашивали рыцаря, он указал на лжеца, 
если лжеца, он указал на рыцаря, 
если дипломата, то среди тех двоих нет дипломатов.

Если спросить дипломата, то он (случайным образом) может ответить и как рыцарь, и как лжец. И как понять, Это рыцарь сказал правду или же
дипломат ответил как рыцарь ?

Я знаю другую задачку, похожую — про рай и ад. Опубликую отдельно =)

Здравствуйте, lexer_lx, Вы писали:

_>Я посмотрел различные ответы, но не понимаю, как их авторы хотели выявить "Произвольного" на основании его "произвольных" ответов ?
_>

_>Спрашиваем первого, кто из оставшихся лживее.
_>Утверждение: тот, на кого укажут, НЕ дипломат:
_>если мы спрашивали рыцаря, он указал на лжеца, 
_>если лжеца, он указал на рыцаря, 
_>если дипломата, то среди тех двоих нет дипломатов.
_>

_>Если спросить дипломата, то он (случайным образом) может ответить и как рыцарь, и как лжец. И как понять, Это рыцарь сказал правду или же
_>дипломат ответил как рыцарь ?

Спасибо, что подняли эту интересную задачу

У кого бы ни спрашивали, среди двух оставшихся один обязательно будет не дипломат:
— рыцать укажет на лжеца
— лжец укажет на рыцаря
— дипломат укажет неважно на кого — среди двух оставшихся дипломата нет

_>Я знаю другую задачку, похожую — про рай и ад. Опубликую отдельно =)

Задачу в студию.

Здравствуйте, lexer_lx, Вы писали:

_>Если спросить дипломата, то он (случайным образом) может ответить и как рыцарь, и как лжец. И как понять, Это рыцарь сказал правду или же
_>дипломат ответил как рыцарь ?

Вы не поняли. Дипломата одназначно определяют по первым двум вопросам, а не по одному.
То есть верно утверждение: тот на кого укажут не дипломат. Тогда спросив вторым вопросом того, на кого указали в первом,
мы получим только одного человека на котрого еще не указали. Он и есть дипломат. Зная это, надо адресовать третий вопрос адресовать не дипломату, спросив его, "Является ли дипломатом дипломат?"

Здравствуйте, baily, Вы писали:

B>Здравствуйте, lexer_lx, Вы писали:

_>>Если спросить дипломата, то он (случайным образом) может ответить и как рыцарь, и как лжец. И как понять, Это рыцарь сказал правду или же
_>>дипломат ответил как рыцарь ?

B>Вы не поняли. Дипломата одназначно определяют по первым двум вопросам, а не по одному.
B>То есть верно утверждение: тот на кого укажут не дипломат. Тогда спросив вторым вопросом того, на кого указали в первом,
B>мы получим только одного человека на котрого еще не указали. Он и есть дипломат. Зная это, надо адресовать третий вопрос адресовать не дипломату, спросив его, "Является ли дипломатом дипломат?"

Понял все. Очень интересная задача и ее решение не менее остроумно =)

Здравствуйте, gloomy rocker,
По-моему, чтоб не мудрить лучше вспомнить старую школьную задачку про три ящика с чёрными, белыми, и чёрными и белыми шариками. На каждом табличка "Чёрные", "Белые", "Чёрные и белые". Известно, что ни одна из табличек не соответствует содержанию ящика. Привести Вашу задачу к подобному виду несложно. Само же решение этой задачи ещё проще.

Здравствуйте, Checkist82, Вы писали:

C>Здравствуйте, gloomy rocker,
C>По-моему, чтоб не мудрить лучше вспомнить старую школьную задачку про три ящика с чёрными, белыми, и чёрными и белыми шариками. На каждом табличка "Чёрные", "Белые", "Чёрные и белые". Известно, что ни одна из табличек не соответствует содержанию ящика. Привести Вашу задачу к подобному виду несложно. Само же решение этой задачи ещё проще.

А можно подробнее? Хотелось бы видеть постановку задачи с математической точностью. Что нужно сделать, за сколько попыток, какие ограничения и т.д.