синє коло

[sassa_nf]

Троє людей прийшли до мудреця, щоб дізнатись, хто з них найрозумніший. Мудрець запропонував задачу: "Я зав'яжу вам очі, намалюю на чолі синє або зелене коло, а потім зніму пов'язки. Якщо бачите синє коло, піднімайте руку. Перший з вас, хто скаже колір кола на їхньому чолі і є найрозумнішим із вас

Comments

[zeit_raffer]

Я не раз видел такие задачи. Приводимые в них решения меня никогда не удовлетворяли. Они предполагают, что каждый человек пользуется довольно непростой немонотонной логикой, причем на каждом такте рассуждения ответ меняется, и еще мы каким-то способом знаем, на каком такте рассуждения находятся остальные учасьники, хотя очевидно, что мы этого не знаем.

[sassa_nf]

race condition как он есть, да.

По-моему, там можно выразить "от противного" - в этом смысле "ответ меняется".

[nponeccop]

Ну это же не логические задачи, а моделирование распределённых систем. Обедающие философы. И, соответственно, темпоральные логики и исчисления процессов, всякие TLA

[zeit_raffer]

> Тогда после двух "не знаю" третий будет "у меня синий", безо всяких кондишенов.

В таком варианте - да, и можно свести просто к предикатам. Главное, чтобы по тактам.

А в исходной формулировке с мудрецами, когда они просто молчат, четкого рассуждения не очень получаются - якобы один шибко вумный и догадался, а остальные якобы "дебилы, бл*".

[nponeccop]

Если говорить в терминах теории моделей - исходная теория симметрична, и несимметричные утверждения в ней невыводимы.

Соответственно, лучший ответ (который в-общем и требуется) - это доказать, что авторы мудаки - т.е. что конкретно это утверждение невыводимо, но satisfiable. Как доказать что satisfiable? Просто доказать, что модели существуют, т.е. предложить (какую-нибудь) модель. Т.е. годятся все варианты - как с дебилами, так и с нумерацией. Желательно при этом пользоваться бритвой Оккама, и конечно мнения проверяющего, чья бритва острее - чистый произвол.

[sassa_nf]

ну а если такт один?

Типа так: если кто-то видит зеленый, он решает, какой у него цвет. Раз никто не решил, значит, никто не видит зеленого. Да, завершенность глагола "решил" означает, что нужно угадывать, должно ли было завершиться вычисление ответа, если бы видел зеленый.

[dmytrish]

Ем, нормально. У Ненсі Лінч розподілені системи якраз діляться на синхронні (все відбувається потактово, існує глобальний дискретний годинник), асинхронні (глобальний годинник відсутній, таймаути необмежені), і асинхронні із таймаутом (middle ground між першими двома моделями, який поєднує більшу визначеність першої моделі із реалістичністю другої

[zeit_raffer]

Якщо вважати, що умова задачі - це те що написано буквально, то про "він знає розподіл часу вирішення для інших" нічого не написано ж. Якщо ж, з іншого боку, є явні такти, коли перші кажуть "не знаю!", то після двох "не знаю" третій має зробити висновок "знаю!" із зрозумілих причин.