![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
праздные размышления о лифтах
Jan. 31st, 2005 01:33 pmЗадача, порождённая опытом, скорее всего тривиальная.
Два человека договорились встретиться у определённого лифта, курсирующего между двумя этажами. На лестничной площадке есть два лифта, соединяющих эти этажи. Но они забыли договориться, на каком из этажей они встречаются. Один из них пришёл и думает: что если второй уже пришёл и ждёт на другом этаже? Спускается проверить, там второго нет; если он сейчас поедет обратно, что если второй уже пришёл и как раз в это время поедет на другой этаж на параллельном лифте? Что если они разминутся так один раз, а потом ещё и ещё? Ясно, что вероятность этого в реальной жизни ничтожна, но есть ли у них алгоритм, гарантирующий в любом случае, что они встретятся?
Ну, во-первых, ясно, что есть; например, они могут договориться заранее, что будут ждать друг друга на верхнем этаже, независимо от того, на какой из этажей вначале придут. Или что будут пользоваться для проверки определённым лифтом, одним из двух.
Значит, чтобы получить нетривиальную задачу, надо усложнить им жизнь. Предположим, что этажи невозможно отличить друг от друга, они выглядят идентично и совершенно симметрично относительно лифта (например, лифт горизонтальный, или всё это происходит в космическом пространстве, и у них нет возможности определить направление движения как "вверх" или "вниз"). Оба лифта тоже невозможно отличить один от другого (например, пусть площадка будет идеально круглая, и лифты находятся строго напротив друг друга, а то место на окружности, через которое они попадают на площадку, заранее неизвестно и может быть разным для обоих). Время поездки на лифте от одного этажа до другого полагаем для удобства фиксированным и небольшим по человеческим меркам; выйти/войти в лифт и осмотреться вокруг себя на площадке занимает ноль времени. Что тогда?
Всё равно легко; например, они заранее договариваются, что один из них будет стоять на месте, а другой - разъезжать туда-сюда; так они неизбежно встретятся. Поэтому надо ещё усложнить; заставим их следовать одному и тому же детерминированному алгоритму. Или, иными словами и более изощрённо-научно-фантастически, пусть это будет человек и его двойник. Человек должен заранее придумать алгоритм, потом его клонируют, и обе копии делают то же самое, т.к. они не могут отличить оригинал от копии.
Получилось у меня превратить это в сколько-нибудь нетривиальную задачу? Кажется, я сделал её нерешаемой; если они оба приходят в один и тот же момент на разные этажи, у них теоретически нет возможности встретиться.
Попробуем теперь немного упростить: пусть известно, что они приходят вначале на один и тот же этаж (но, как и раньше, ничего не известно о времени прихода; всего лишь то, что оба рано или поздно придут). Есть тогда тривиальное решение, которое я упускаю, или мне удалось сохранить немного сложности? Впрочем, то нетривиальное решение, которое я придумал для этого случая, всё равно не слишком сложное: ( Read more... )
Возможно, есть ещё какие-то интересные варианты.
Два человека договорились встретиться у определённого лифта, курсирующего между двумя этажами. На лестничной площадке есть два лифта, соединяющих эти этажи. Но они забыли договориться, на каком из этажей они встречаются. Один из них пришёл и думает: что если второй уже пришёл и ждёт на другом этаже? Спускается проверить, там второго нет; если он сейчас поедет обратно, что если второй уже пришёл и как раз в это время поедет на другой этаж на параллельном лифте? Что если они разминутся так один раз, а потом ещё и ещё? Ясно, что вероятность этого в реальной жизни ничтожна, но есть ли у них алгоритм, гарантирующий в любом случае, что они встретятся?
Ну, во-первых, ясно, что есть; например, они могут договориться заранее, что будут ждать друг друга на верхнем этаже, независимо от того, на какой из этажей вначале придут. Или что будут пользоваться для проверки определённым лифтом, одним из двух.
Значит, чтобы получить нетривиальную задачу, надо усложнить им жизнь. Предположим, что этажи невозможно отличить друг от друга, они выглядят идентично и совершенно симметрично относительно лифта (например, лифт горизонтальный, или всё это происходит в космическом пространстве, и у них нет возможности определить направление движения как "вверх" или "вниз"). Оба лифта тоже невозможно отличить один от другого (например, пусть площадка будет идеально круглая, и лифты находятся строго напротив друг друга, а то место на окружности, через которое они попадают на площадку, заранее неизвестно и может быть разным для обоих). Время поездки на лифте от одного этажа до другого полагаем для удобства фиксированным и небольшим по человеческим меркам; выйти/войти в лифт и осмотреться вокруг себя на площадке занимает ноль времени. Что тогда?
Всё равно легко; например, они заранее договариваются, что один из них будет стоять на месте, а другой - разъезжать туда-сюда; так они неизбежно встретятся. Поэтому надо ещё усложнить; заставим их следовать одному и тому же детерминированному алгоритму. Или, иными словами и более изощрённо-научно-фантастически, пусть это будет человек и его двойник. Человек должен заранее придумать алгоритм, потом его клонируют, и обе копии делают то же самое, т.к. они не могут отличить оригинал от копии.
Получилось у меня превратить это в сколько-нибудь нетривиальную задачу? Кажется, я сделал её нерешаемой; если они оба приходят в один и тот же момент на разные этажи, у них теоретически нет возможности встретиться.
Попробуем теперь немного упростить: пусть известно, что они приходят вначале на один и тот же этаж (но, как и раньше, ничего не известно о времени прихода; всего лишь то, что оба рано или поздно придут). Есть тогда тривиальное решение, которое я упускаю, или мне удалось сохранить немного сложности? Впрочем, то нетривиальное решение, которое я придумал для этого случая, всё равно не слишком сложное: ( Read more... )
Возможно, есть ещё какие-то интересные варианты.
![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif){kind=small}