Едет поезд с пассажирами, количество неизвестно. Каждый из них видит всех остальных, но не видит самого себя. После того как поезд заедет в туннель, некоторые из пассажиров запачкаются. Затем в вагон заходит проводник и говорит: "Когда кто-то из вас будет уверен, что он запачкался, пусть на следующей остановке выйдет". Вопрос: на какой остановке ( min ) выйдут все запачкавшиеся, если их N и все действуют по одинаковому алгоритму?

задан 27 Авг '19 6:44

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

(27 Авг '19 6:45) sapere aude
10|600 символов нужно символов осталось
2

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

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

Посмотрим, как рассуждают пассажиры, обозначая их A, B, C. Пассажир A видит перед собой двух чёрных, а свой цвет он не знает. И рассуждает от противного, допуская, что он белый. Далее он ставит себя на место B, то есть в его представлении, B должен рассуждать так. Он видит белого A и чёрного C. Свой цвет он не знает, и допускает, что он белый. Ставя себя на место C, пассажир B смотрит на ситуацию его глазами, и понимает, что С видит двух белых. Тогда, зная от проводника, что чёрные среди троих есть, через 1 остановку C должен выйти.

Проходит время, но C не выходит. Тогда B от противного приходит к выводу, что его предположение ложно. Значит, он логически выводит, что он чёрный. И тогда он должен выйти на второй остановке. Вспомним, что всё это происходит в рассуждении A. После двух остановок никто не выходит. Значит, A делает вывод, что его допущение неверно. То есть он чёрный.

К такому выводу приходит каждый из пассажиров к моменту 3-й остановки. То есть все они на ней должны выйти. Если пассажиров N, и все они запачканы, то всё ровно то же самое происходит на N-м шаге.

Теперь надо объяснить парадокс. Что произошло, почему сообщение известных каждому сведений повлекло за собой цепочку выводов и следствий? Рассмотрим следующий бесконечный набор пронумерованных утверждений.

0) среди пассажиров есть чёрные

1) все знают, что утверждение 0) верно

2) все знают, что утверждение 1) верно

3) все знают, что утверждение 2) верно

.....

и так далее. Проводник сообщает всем утверждение 0), но это происходит публично. То есть все слышали, что 0) верно. Подразумевается, что сообщена истина, и что ей полагается верить. Тем самым, утверждение 1) верно, и об этом в силу публичности все знают. Отсюда следует, что 2) верно, и об этом все осведомлены. Получается по цепочке, что все утверждения верны, и каждый об этом знает. То есть тут возникает эффект типа "я знаю, что ты знаешь, что я знаю".

Если бы проводник ничего не сообщал, а кто-то видит хотя бы одного чёрного, то он знает, что чёрные среди пассажиров есть, то есть 0) верно. Если он видит двух чёрных, то каждый видит хотя бы одного чёрного, то есть 0) знают все, и тогда 1) верно. Но все ли знают, что 1) верно? Нет, потому что если A белый, то B и C уже не видят двух чёрных, и тогда об истинности пункта 1) они не знают, то есть 2) неверно. Здесь видна разница между состоянием знаний до сообщения проводника и после.

Такого рода вещи, наряду с другими логическими парадоксами (типа Парадокса Монти Холла, или Парадокса Неожиданной Казни) часто обсуждаются в каких-то статьях, или занимательных книжках, или просто в Сети. Есть даже понятие "общего знания", когда все знают, что все знают, что все знают, что ... верно X. Правда, это всё, будучи известным, вряд ли может служить предметом пособий по решению "типовых" задач. А основой служит обычная логика, правила которой всем известны. Тут надо только преодолеть некий психологический барьер, состоящий в разрешении рассуждать, когда возникает что-то непривычное типа "сказки про белого бычка". Люди часто склонны подобные рассуждения "блокировать", а тогда ничего не получается.

ссылка

отвечен 27 Авг '19 11:32

@falcao, большое спасибо!

(27 Авг '19 11:43) Казвертеночка
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,404
×501
×90
×3

задан
27 Авг '19 6:44

показан
246 раз

обновлен
27 Авг '19 11:43

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru