Едет поезд с пассажирами, количество неизвестно. Каждый из них видит всех остальных, но не видит самого себя. После того как поезд заедет в туннель, некоторые из пассажиров запачкаются. Затем в вагон заходит проводник и говорит:
"Когда кто-то из вас будет уверен, что он запачкался, пусть на следующей остановке выйдет".
Вопрос: на какой остановке ( min ) выйдут все запачкавшиеся, если их N и все действуют по одинаковому алгоритму?
Здравствуйте, YO-LKA, Вы писали:
YL>Едет поезд с пассажирами, количество неизвестно. Каждый из них видит всех остальных, но не видит самого себя. После того как поезд заедет в туннель, некоторые из пассажиров запачкаются. Затем в вагон заходит проводник и говорит: YL>"Когда кто-то из вас будет уверен, что он запачкался, пусть на следующей остановке выйдет". YL>Вопрос: на какой остановке ( min ) выйдут все запачкавшиеся, если их N и все действуют по одинаковому алгоритму?
Если проводник назвал количество грязных, — то все они выйдут на первой же остановке (я грязный если я вижу N-1 грязных).
Если у всех пассажиров одинаковая прозорливость — то все грязные догадаются о том, что они грязные, одновременно. И опять же выйдут на одной остановке. Возможно, что не на первой...
Если ситуация неразрешима (хреново у граждан с прозорливостью) — разойдутся по своим остановкам, что выходит за пределы описания задачи.
Здравствуйте, YO-LKA, Вы писали:
YL>Здравствуйте, Кодт, Вы писали:
YL>Ну делов в том что проводник не называет количества запачкавшихся пасожиров YL>и вопрос в том на какой остановке сойдет последний из них
В силу симметричности задачи относительно каждого грязного пассажира (да и относительно чистых тоже) ни один из них не имеет преимущества перед остальными.
Значит, до них "дойдет" в одно и то же время, поэтому и ломанутся в дверь они на одной остановке.
Как долго до них будет доходить — это уже дело десятое.
Здравствуйте, YO-LKA, Вы писали:
YL>ну я же сказал что задачка ПРИКОЛЬНЕАЯ YL>таво что я сказал даже больше чем достаточно для того чтоб сказать YL>на какой станции они выходят
Здравствуйте, YO-LKA, Вы писали:
YL> Здрасть вот такая прикольная задачка YL> YL> Едет поезд с пассажирами, количество неизвестно. Каждый из них видит YL> всех остальных, но не видит самого себя. После того как поезд заедет в YL> туннель, некоторые из пассажиров запачкаются. Затем в вагон заходит YL> проводник и говорит: "Когда кто-то из вас будет уверен, что он YL> запачкался, пусть на следующей остановке выйдет". Вопрос: на какой YL> остановке ( min ) выйдут все запачкавшиеся, если их N и все действуют YL> по одинаковому алгоритму? YL>
Странный поезд и странные пассажиры. Что они такого делают в тоннеле, что потом "некоторые" испачканы???
А ответ, видимо, на конечной.
-- Всего хорошего!
-- Alex Alexandrov, e-mail: alexandrov_alex@fromru.com
Posted via RSDN NNTP Server 1.7 "Bedlam"
It's kind of fun to do the impossible (Walt Disney)
Здравствуйте, YO-LKA! Вы писали:
YL> Не не на конечной остановки безконечные (задача имеет решение ) YL> зы а приколная потому что она легкая но кажется не решаемой
Здравствуйте, YO-LKA, Вы писали:
YL> Здравствуйте, alexandrov_alex, Вы писали: YL> YL> Не не на конечной остановки безконечные (задача имеет решение ) YL> зы а приколная потому что она легкая но кажется не решаемой
Ну давай предположим, что в туннеле обрызгивает всех пассажиров. Раз обрызнуло всех, другой раз всех. И сидят они как дураки все обрызганные, смотрят друг на друга, и думают, выходить им или нет. И что?
В общем, не томи социум — ответ давай.
-- Всего хорошего!
-- Alex Alexandrov, e-mail: alexandrov_alex@fromru.com
Posted via RSDN NNTP Server 1.7 "Bedlam"
It's kind of fun to do the impossible (Walt Disney)
Здравствуйте, YO-LKA, Вы писали: YL>Вопрос: на какой остановке ( min ) выйдут все запачкавшиеся, если их N и все действуют по одинаковому алгоритму?
Вопрос из серии что где когда на внимательность...
Ключи к ответу (выделены):
1) "Когда кто-то из вас будет уверен, что он запачкался, пусть на следующей остановке выйдет".
и
2) на какой остановке ( min ) выйдут все запачкавшиеся?
Ответ: если все соображают быстро, то выйдут на следующей.
Здравствуйте, av_lazarev, Вы писали:
_>Вопрос из серии что где когда на внимательность... _>Ключи к ответу (выделены): _>1) "Когда кто-то из вас будет уверен, что он запачкался, пусть на следующей остановке выйдет". _>и _>2) на какой остановке ( min ) выйдут все запачкавшиеся?
_>Ответ: если все соображают быстро, то выйдут на следующей.
А если этто пыыл финнский поезд? Или там неуверенные люди ездят? И есть ли вообще способ придать им эту уверенность?
Здравствуйте, av_lazarev! Вы писали:
al> Здравствуйте, YO-LKA, Вы писали: YL>> Вопрос: на какой остановке ( min ) выйдут все запачкавшиеся, если их N YL>> и все действуют по одинаковому алгоритму?
al> Вопрос из серии что где когда на внимательность... al> Ключи к ответу (выделены): al> 1) "Когда кто-то из вас будет уверен, что он запачкался, пусть на al> следующей остановке выйдет". и al> 2) на какой остановке ( min ) выйдут все запачкавшиеся?
al> Ответ: если все соображают быстро, то выйдут на следующей.
А если ехал один человек? У него вообще нет шансов узнать о своей чистоте!
Задача известная, поэтому я и молчал. Но раз никто не дал ответа...
Запачкавшиеся выдут на N-ой остановке.
Доказываем по индукции:
N=1
Запачкавшийся: Все пассажиры, которых я вижу чистые. Следовательно грязный я и мне надо выйти на первой же остановке.
Чистый: Сначала я не знаю грязный ли я, но после того как единственный из запачкавшихся вышел на превой остановке, я знаю, что он видел только чистых. Следовательно я чистый.
N=N
Запачкавшийся: Я вижу N-1 грязных пассажиров, раз они не вышли на N-1 остановке, следовательно я грязный.
Чистый: Видит N грязных. Т.к. они все вышли на N-ой остановке, следовательно всего их N и я чистый.
Здравствуйте, MichaelP, Вы писали:
MP>Задача известная, поэтому я и молчал. Но раз никто не дал ответа...
MP>Запачкавшиеся выдут на N-ой остановке.
MP>Доказываем по индукции: MP>N=1 MP>Запачкавшийся: Все пассажиры, которых я вижу чистые. Следовательно грязный я и мне надо выйти на первой же остановке. MP>Чистый: Сначала я не знаю грязный ли я, но после того как единственный из запачкавшихся вышел на превой остановке, я знаю, что он видел только чистых. Следовательно я чистый.
MP>N=N MP>Запачкавшийся: Я вижу N-1 грязных пассажиров, раз они не вышли на N-1 остановке, следовательно я грязный. MP>Чистый: Видит N грязных. Т.к. они все вышли на N-ой остановке, следовательно всего их N и я чистый.
Ха. Некорректная индукция.
N=1. Первый перегон. Грязный видит только чистых (далее — 0) — следовательно, он грязный. Чистые видят 1.
N=2. Первый перегон. Грязные видят 1, чистые видят 2.
То есть ситуации (N=2, я грязный) и (N=1, я чистый) субъективно неразличимы.
К>N=1. Первый перегон. Грязный видит только чистых (далее — 0) — следовательно, он грязный. Чистые видят 1. К>N=2. Первый перегон. Грязные видят 1, чистые видят 2. К>То есть ситуации (N=2, я грязный) и (N=1, я чистый) субъективно неразличимы.
Они не различимы на первом прегоне. На втором прегоне мы уже имеем информацию, что пассажир не вышел(или вышел). Следовательно N!=1, откуда N=2, я грязный (или N=1, я чистый).
Здравствуйте, MichaelP, Вы писали:
MP>Здравствуйте, Кодт, Вы писали:
К>>N=1. Первый перегон. Грязный видит только чистых (далее — 0) — следовательно, он грязный. Чистые видят 1. К>>N=2. Первый перегон. Грязные видят 1, чистые видят 2. К>>То есть ситуации (N=2, я грязный) и (N=1, я чистый) субъективно неразличимы. MP>Они не различимы на первом прегоне. На втором прегоне мы уже имеем информацию, что пассажир не вышел(или вышел). Следовательно N!=1, откуда N=2, я грязный (или N=1, я чистый).
Ааа!
Причем все грязные дружно встают и выходят на N'ной остановке.
Фактически, на K'й остановке пассажиры сообщают друг другу: мы видим не менее K грязных. Соответственно, для понимания своей грязности человеку нужно "услышать" что сейчас не менее K грязных, но я вижу ровно K-1.