Прикольная задачка: грязные пассажиры
От: YO-LKA  
Дата: 07.10.03 14:40
Оценка:
Здрасть вот такая прикольная задачка

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

поправлена орфография. — К
Re: Прикольная задачка: грязные пассажиры
От: Кодт Россия  
Дата: 07.10.03 15:52
Оценка:
Здравствуйте, YO-LKA, Вы писали:

YL>Едет поезд с пассажирами, количество неизвестно. Каждый из них видит всех остальных, но не видит самого себя. После того как поезд заедет в туннель, некоторые из пассажиров запачкаются. Затем в вагон заходит проводник и говорит:

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

Если проводник назвал количество грязных, — то все они выйдут на первой же остановке (я грязный если я вижу N-1 грязных).

Если у всех пассажиров одинаковая прозорливость — то все грязные догадаются о том, что они грязные, одновременно. И опять же выйдут на одной остановке. Возможно, что не на первой...

Если ситуация неразрешима (хреново у граждан с прозорливостью) — разойдутся по своим остановкам, что выходит за пределы описания задачи.
Перекуём баги на фичи!
Re[2]: Прикольная задачка: грязные пассажиры
От: YO-LKA  
Дата: 07.10.03 16:11
Оценка:
Здравствуйте, Кодт, Вы писали:

Ну делов в том что проводник не называет количества запачкавшихся пасожиров
и вопрос в том на какой остановке сойдет последни из них
Re[3]: Прикольная задачка: грязные пассажиры
От: Кодт Россия  
Дата: 07.10.03 16:16
Оценка:
Здравствуйте, YO-LKA, Вы писали:

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


YL>Ну делов в том что проводник не называет количества запачкавшихся пасожиров

YL>и вопрос в том на какой остановке сойдет последний из них

В силу симметричности задачи относительно каждого грязного пассажира (да и относительно чистых тоже) ни один из них не имеет преимущества перед остальными.
Значит, до них "дойдет" в одно и то же время, поэтому и ломанутся в дверь они на одной остановке.
Как долго до них будет доходить — это уже дело десятое.
Перекуём баги на фичи!
Re[4]: Прикольная задачка: грязные пассажиры
От: YO-LKA  
Дата: 07.10.03 16:25
Оценка:
то что они выдут одновремено ето верно
НО ВОПРОС : нА КАКОЙ СТАНЦИИ ОНИ СОЙДУТ (НОМЕР)
Re[5]: Прикольная задачка: грязные пассажиры
От: Кодт Россия  
Дата: 07.10.03 16:41
Оценка:
Здравствуйте, YO-LKA, Вы писали:

YL>то что они выдут одновремено ето верно

YL>НО ВОПРОС : нА КАКОЙ СТАНЦИИ ОНИ СОЙДУТ (НОМЕР)

Будут быстро думать — на первой
Или ты что-то не договариваешь...
Перекуём баги на фичи!
Re[6]: Прикольная задачка: грязные пассажиры
От: YO-LKA  
Дата: 07.10.03 16:50
Оценка:
ну я же сказал что задачка ПРИКОЛЬНЕАЯ
таво что я сказал даже больше чем достаточно для того чтоб сказать
на какой станции они выходят
Re[7]: Прикольная задачка: грязные пассажиры
От: Real 3L0 Россия http://prikhodko.blogspot.com
Дата: 08.10.03 01:23
Оценка: +1 :))
Здравствуйте, YO-LKA, Вы писали:

YL>ну я же сказал что задачка ПРИКОЛЬНЕАЯ

YL>таво что я сказал даже больше чем достаточно для того чтоб сказать
YL>на какой станции они выходят

Ну значит выйдут они на ПРИКОЛЬНЕАЙ остановке!
... << Posted by RSDN@Home 1.1 beta 2 >>
Вселенная бесконечна как вширь, так и вглубь.
Re: Прикольная задачка: грязные пассажиры
От: alexandrov_alex США  
Дата: 08.10.03 06:49
Оценка: :)
Здравствуйте, 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)
Re[2]: Прикольная задачка: грязные пассажиры
От: YO-LKA  
Дата: 08.10.03 12:54
Оценка:
Здравствуйте, alexandrov_alex, Вы писали:

Не не на конечной остановки безконечные (задача имеет решение )
зы а приколная потому что она легкая но кажется не решаемой
Re[3]: Прикольная задачка: грязные пассажиры
От: GarryIV  
Дата: 08.10.03 13:31
Оценка: :)
Здравствуйте, YO-LKA! Вы писали:

YL> Не не на конечной остановки безконечные (задача имеет решение )

YL> зы а приколная потому что она легкая но кажется не решаемой

Сдается мне что ты гонишь...
Posted via RSDN NNTP Server 1.7 "Bedlam"
WBR, Igor Evgrafov
Re[3]: Прикольная задачка: грязные пассажиры
От: alexandrov_alex США  
Дата: 08.10.03 13:42
Оценка: +1 :))
Здравствуйте, 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)
Re: Прикольная задачка: грязные пассажиры
От: av_lazarev  
Дата: 08.10.03 13:48
Оценка:
Здравствуйте, YO-LKA, Вы писали:
YL>Вопрос: на какой остановке ( min ) выйдут все запачкавшиеся, если их N и все действуют по одинаковому алгоритму?

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

Ответ: если все соображают быстро, то выйдут на следующей.
... << RSDN@Home 1.1 beta 2 >>
Re[2]: Прикольная задачка: грязные пассажиры
От: Кодт Россия  
Дата: 08.10.03 14:03
Оценка:
Здравствуйте, av_lazarev, Вы писали:

_>Вопрос из серии что где когда на внимательность...

_>Ключи к ответу (выделены):
_>1) "Когда кто-то из вас будет уверен, что он запачкался, пусть на следующей остановке выйдет".
_>и
_>2) на какой остановке ( min ) выйдут все запачкавшиеся?

_>Ответ: если все соображают быстро, то выйдут на следующей.


А если этто пыыл финнский поезд? Или там неуверенные люди ездят? И есть ли вообще способ придать им эту уверенность?
Перекуём баги на фичи!
Re[3]: Прикольная задачка: грязные пассажиры
От: av_lazarev  
Дата: 08.10.03 14:15
Оценка:
Здравствуйте, Кодт, Вы писали:

К>А если этто пыыл финнский поезд? Или там неуверенные люди ездят? И есть ли вообще способ придать им эту уверенность?


Ну в случае финнского поезда — то конечная
... << RSDN@Home 1.1 beta 2 >>
Re[2]: Прикольная задачка: грязные пассажиры
От: GarryIV  
Дата: 08.10.03 15:51
Оценка:
Здравствуйте, av_lazarev! Вы писали:

al> Здравствуйте, YO-LKA, Вы писали:

YL>> Вопрос: на какой остановке ( min ) выйдут все запачкавшиеся, если их N
YL>> и все действуют по одинаковому алгоритму?

al> Вопрос из серии что где когда на внимательность...

al> Ключи к ответу (выделены):
al> 1) "Когда кто-то из вас будет уверен, что он запачкался, пусть на
al> следующей остановке выйдет". и
al> 2) на какой остановке ( min ) выйдут все запачкавшиеся?

al> Ответ: если все соображают быстро, то выйдут на следующей.


А если ехал один человек? У него вообще нет шансов узнать о своей чистоте!

Вобщем это плохая задача. ИМХО.
Posted via RSDN NNTP Server 1.7 "Bedlam"
WBR, Igor Evgrafov
Re: Прикольная задачка: грязные пассажиры
От: MichaelP  
Дата: 09.10.03 08:35
Оценка: 3 (1)
Задача известная, поэтому я и молчал. Но раз никто не дал ответа...

Запачкавшиеся выдут на N-ой остановке.

Доказываем по индукции:
N=1
Запачкавшийся: Все пассажиры, которых я вижу чистые. Следовательно грязный я и мне надо выйти на первой же остановке.
Чистый: Сначала я не знаю грязный ли я, но после того как единственный из запачкавшихся вышел на превой остановке, я знаю, что он видел только чистых. Следовательно я чистый.

N=N
Запачкавшийся: Я вижу N-1 грязных пассажиров, раз они не вышли на N-1 остановке, следовательно я грязный.
Чистый: Видит N грязных. Т.к. они все вышли на N-ой остановке, следовательно всего их N и я чистый.
Re[2]: Прикольная задачка: грязные пассажиры
От: Кодт Россия  
Дата: 09.10.03 08:46
Оценка:
Здравствуйте, 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, я чистый) субъективно неразличимы.
  • Перекуём баги на фичи!
    Re[3]: Прикольная задачка: грязные пассажиры
    От: MichaelP  
    Дата: 09.10.03 09:03
    Оценка: 10 (1)
    Здравствуйте, Кодт, Вы писали:


    К>
  • N=1. Первый перегон. Грязный видит только чистых (далее — 0) — следовательно, он грязный. Чистые видят 1.
    К>
  • N=2. Первый перегон. Грязные видят 1, чистые видят 2.
    К>То есть ситуации (N=2, я грязный) и (N=1, я чистый) субъективно неразличимы.
    Они не различимы на первом прегоне. На втором прегоне мы уже имеем информацию, что пассажир не вышел(или вышел). Следовательно N!=1, откуда N=2, я грязный (или N=1, я чистый).
  • Re[4]: Прикольная задачка: грязные пассажиры
    От: Кодт Россия  
    Дата: 09.10.03 09:16
    Оценка: 5 (1)
    Здравствуйте, MichaelP, Вы писали:

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



    К>>
  • N=1. Первый перегон. Грязный видит только чистых (далее — 0) — следовательно, он грязный. Чистые видят 1.
    К>>
  • N=2. Первый перегон. Грязные видят 1, чистые видят 2.
    К>>То есть ситуации (N=2, я грязный) и (N=1, я чистый) субъективно неразличимы.
    MP>Они не различимы на первом прегоне. На втором прегоне мы уже имеем информацию, что пассажир не вышел(или вышел). Следовательно N!=1, откуда N=2, я грязный (или N=1, я чистый).

    Хорошо же.
    N=1, T=1. грязный(0), чистые(1) — грязный выходит.
    N=2. T=1. грязные(1), чистые(2) — сидят все. T=2. грязные(1), чистые(2) — грязные выходят.
    N=3. T=2. грязные(2), чистые(3) — сидят. T=3...

    Ааа!
    Причем все грязные дружно встают и выходят на N'ной остановке.

    Фактически, на K'й остановке пассажиры сообщают друг другу: мы видим не менее K грязных. Соответственно, для понимания своей грязности человеку нужно "услышать" что сейчас не менее K грязных, но я вижу ровно K-1.
  • Перекуём баги на фичи!
    Подождите ...
    Wait...
    Пока на собственное сообщение не было ответов, его можно удалить.