Здравствуйте, YO-LKA, Вы писали:
YL>Здрасть вот такая прикольная задачка
Где-то я эту задачку видел в более удачной формулировке. 13 мудрецов называлась.
---
С уважением,
Лазарев Андрей
Re[5]: Поправочка...
От:
Аноним
Дата:
10.10.03 14:12
Оценка:
Здравствуйте, Кодт, Вы писали:
К>Фактически, на K'й остановке пассажиры сообщают друг другу: мы видим не менее K грязных. Соответственно, для понимания своей грязности человеку нужно "услышать" что сейчас не менее K грязных, но я вижу ровно K-1.
Всё это было бы так замечательно, если бы не один пустячок.
В приведённой формулировке (имхо автор это просто забыл )
ПРОВОДНИК НЕ СООБЩАЕТ, ЧТО В ВАГОНЕ ИМЕЮТСЯ ГРЯЗНЫЕ.
Он просто говорит мол если кто будет уверен, выйдите.
Поэтому даже если он там один грязный,
он вовсе не соберётся выйти на ближайшей остановке.
Откуда ему быть уверенным?
MichaelP совершенно прав, что задача известнейшая —
я её слышал в варианте неверных жён...
Здравствуйте, Кодт, Вы писали:
К>Фактически, на K'й остановке пассажиры сообщают друг другу: мы видим не менее K грязных. Соответственно, для понимания своей грязности человеку нужно "услышать" что сейчас не менее K грязных, но я вижу ровно K-1.
Имхо, если грязных не менее 4, то они никогда не выйдут.
Рассуждения по похожей задаче смотреть здесь
Pro gnomov i kolpaki krasnie i sinie. U menya ushlo minut 5 na reshenie. Jena reshila za 5 sekund V sluh bilo prikol'no. Tipa N s kolpokami plyus odin... I tut pauza sekundi na tri I ne programist, a yurist. A vot i bivaet i takoe
Здравствуйте, YO-LKA, Вы писали:
YL>Здрасть вот такая прикольная задачка
YL>Едет поезд с пассажирами, количество неизвестно. Каждый из них видит всех остальных, но не видит самого себя. После того как поезд заедет в туннель, некоторые из пассажиров запачкаются. Затем в вагон заходит проводник и говорит: YL>"Когда кто-то из вас будет уверен, что он запачкался, пусть на следующей остановке выйдет". YL>Вопрос: на какой остановке ( min ) выйдут все запачкавшиеся, если их N и все действуют по одинаковому алгоритму?
Предположим, что пассажирам известно что есть по крайней мере один грязный.
Вот, как должен рассуждать каждый из них:
1. Все вокруг меня чистые, значит грязный один я.
Выходит на первой остановке со словами "в следующий раз полечу самолётом"
2. Я вижу 1 грязного человека. Если он не выходит на первой остановке значит он тоже видит одного грязного — меня. Поскольку он думает точно так же, то мы с ним вдвоём сойдём с поезда на второй остановке.
3. Я вижу 2 грязных людей. Если я чистый — значит каждый из них видит только одного грязного и сойдёт на второй остановке согласно пункту 2. Если на второй остановке никто не сходит значит я грязный и поскольку они рассуждают точно так же, мы все втроём сойдём на третей остановке.
.
.
.
.
X. Я вижу X грязных людей. Если я чистый — значит каждый из них видит только X-1 грязных людей и все они сойдут на x-1 остановке согласно пункту X-1. О-па! Они не сошли? Значит они видят больше грязных людей. Значит я грязный!! Сойду на следующей остановке.
Итого. Обычная индукция. Все выйдут на остановке номер N. (хотя на самом деле, гораздо логичней было бы пойти умыться. Видимо действительно финнский поезд)
) 
