праздные размышления о лифтах
Jan. 31st, 2005 01:33 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaЗадача, порождённая опытом, скорее всего тривиальная.
Два человека договорились встретиться у определённого лифта, курсирующего между двумя этажами. На лестничной площадке есть два лифта, соединяющих эти этажи. Но они забыли договориться, на каком из этажей они встречаются. Один из них пришёл и думает: что если второй уже пришёл и ждёт на другом этаже? Спускается проверить, там второго нет; если он сейчас поедет обратно, что если второй уже пришёл и как раз в это время поедет на другой этаж на параллельном лифте? Что если они разминутся так один раз, а потом ещё и ещё? Ясно, что вероятность этого в реальной жизни ничтожна, но есть ли у них алгоритм, гарантирующий в любом случае, что они встретятся?
Ну, во-первых, ясно, что есть; например, они могут договориться заранее, что будут ждать друг друга на верхнем этаже, независимо от того, на какой из этажей вначале придут. Или что будут пользоваться для проверки определённым лифтом, одним из двух.
Значит, чтобы получить нетривиальную задачу, надо усложнить им жизнь. Предположим, что этажи невозможно отличить друг от друга, они выглядят идентично и совершенно симметрично относительно лифта (например, лифт горизонтальный, или всё это происходит в космическом пространстве, и у них нет возможности определить направление движения как "вверх" или "вниз"). Оба лифта тоже невозможно отличить один от другого (например, пусть площадка будет идеально круглая, и лифты находятся строго напротив друг друга, а то место на окружности, через которое они попадают на площадку, заранее неизвестно и может быть разным для обоих). Время поездки на лифте от одного этажа до другого полагаем для удобства фиксированным и небольшим по человеческим меркам; выйти/войти в лифт и осмотреться вокруг себя на площадке занимает ноль времени. Что тогда?
Всё равно легко; например, они заранее договариваются, что один из них будет стоять на месте, а другой - разъезжать туда-сюда; так они неизбежно встретятся. Поэтому надо ещё усложнить; заставим их следовать одному и тому же детерминированному алгоритму. Или, иными словами и более изощрённо-научно-фантастически, пусть это будет человек и его двойник. Человек должен заранее придумать алгоритм, потом его клонируют, и обе копии делают то же самое, т.к. они не могут отличить оригинал от копии.
Получилось у меня превратить это в сколько-нибудь нетривиальную задачу? Кажется, я сделал её нерешаемой; если они оба приходят в один и тот же момент на разные этажи, у них теоретически нет возможности встретиться.
Попробуем теперь немного упростить: пусть известно, что они приходят вначале на один и тот же этаж (но, как и раньше, ничего не известно о времени прихода; всего лишь то, что оба рано или поздно придут). Есть тогда тривиальное решение, которое я упускаю, или мне удалось сохранить немного сложности? Впрочем, то нетривиальное решение, которое я придумал для этого случая, всё равно не слишком сложное: после прихода каждый сначала ждёт одну минуту, потом едет на другой этаж, ждёт там две минуты, едет обратно, ждёт три итп (кажется, этого достаточно, и не надо использовать геометрический ряд в 1-2-4-8-16-... минут)
Возможно, есть ещё какие-то интересные варианты.
Два человека договорились встретиться у определённого лифта, курсирующего между двумя этажами. На лестничной площадке есть два лифта, соединяющих эти этажи. Но они забыли договориться, на каком из этажей они встречаются. Один из них пришёл и думает: что если второй уже пришёл и ждёт на другом этаже? Спускается проверить, там второго нет; если он сейчас поедет обратно, что если второй уже пришёл и как раз в это время поедет на другой этаж на параллельном лифте? Что если они разминутся так один раз, а потом ещё и ещё? Ясно, что вероятность этого в реальной жизни ничтожна, но есть ли у них алгоритм, гарантирующий в любом случае, что они встретятся?
Ну, во-первых, ясно, что есть; например, они могут договориться заранее, что будут ждать друг друга на верхнем этаже, независимо от того, на какой из этажей вначале придут. Или что будут пользоваться для проверки определённым лифтом, одним из двух.
Значит, чтобы получить нетривиальную задачу, надо усложнить им жизнь. Предположим, что этажи невозможно отличить друг от друга, они выглядят идентично и совершенно симметрично относительно лифта (например, лифт горизонтальный, или всё это происходит в космическом пространстве, и у них нет возможности определить направление движения как "вверх" или "вниз"). Оба лифта тоже невозможно отличить один от другого (например, пусть площадка будет идеально круглая, и лифты находятся строго напротив друг друга, а то место на окружности, через которое они попадают на площадку, заранее неизвестно и может быть разным для обоих). Время поездки на лифте от одного этажа до другого полагаем для удобства фиксированным и небольшим по человеческим меркам; выйти/войти в лифт и осмотреться вокруг себя на площадке занимает ноль времени. Что тогда?
Всё равно легко; например, они заранее договариваются, что один из них будет стоять на месте, а другой - разъезжать туда-сюда; так они неизбежно встретятся. Поэтому надо ещё усложнить; заставим их следовать одному и тому же детерминированному алгоритму. Или, иными словами и более изощрённо-научно-фантастически, пусть это будет человек и его двойник. Человек должен заранее придумать алгоритм, потом его клонируют, и обе копии делают то же самое, т.к. они не могут отличить оригинал от копии.
Получилось у меня превратить это в сколько-нибудь нетривиальную задачу? Кажется, я сделал её нерешаемой; если они оба приходят в один и тот же момент на разные этажи, у них теоретически нет возможности встретиться.
Попробуем теперь немного упростить: пусть известно, что они приходят вначале на один и тот же этаж (но, как и раньше, ничего не известно о времени прихода; всего лишь то, что оба рано или поздно придут). Есть тогда тривиальное решение, которое я упускаю, или мне удалось сохранить немного сложности? Впрочем, то нетривиальное решение, которое я придумал для этого случая, всё равно не слишком сложное: после прихода каждый сначала ждёт одну минуту, потом едет на другой этаж, ждёт там две минуты, едет обратно, ждёт три итп (кажется, этого достаточно, и не надо использовать геометрический ряд в 1-2-4-8-16-... минут)
Возможно, есть ещё какие-то интересные варианты.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2005-01-31 11:37 am (UTC)no subject
Date: 2005-01-31 11:44 am (UTC)They also serve who stand and wait.
no subject
Date: 2005-01-31 11:53 am (UTC)no subject
Date: 2005-01-31 11:57 am (UTC)(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:no subject
Date: 2005-01-31 11:38 am (UTC)no subject
Date: 2005-01-31 11:41 am (UTC)(no subject)
From:(no subject)
From:no subject
Date: 2005-01-31 11:52 am (UTC)no subject
no subject
Date: 2005-01-31 11:53 am (UTC)no subject
Date: 2005-01-31 12:19 pm (UTC)(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:no subject
Date: 2005-01-31 11:59 am (UTC)no subject
Date: 2005-01-31 12:19 pm (UTC)no subject
Date: 2005-01-31 12:25 pm (UTC)Именно-именно!
Date: 2005-01-31 05:35 pm (UTC)no subject
Date: 2005-01-31 12:14 pm (UTC)http://www.livejournal.com/community/hitech_tests/3841.html
no subject
Date: 2005-01-31 12:24 pm (UTC)(no subject)
From:no subject
Date: 2005-01-31 12:14 pm (UTC)no subject
Date: 2005-01-31 12:19 pm (UTC)Умеют ли они считать (достаточно знать последовательность чисел, операций не нужно) и могут ли задать лифту в какую сторону ехать и на сколько этажей?
В принципе: куча вариантов этой задачи рассматривается в стандартных курсах "online algorithms" или я что-то неуловила?
no subject
Date: 2005-01-31 12:23 pm (UTC)Варианты наверняка рассматриваются. Это не столько задача, сколько не вполне удавшаяся попытка взять ситуацию из реальной жизни и превратить её в нетривиальную задачу.
(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:no subject
Date: 2005-01-31 12:37 pm (UTC)Вероятностное, кажется, тривиально - собственно, если просто на каждом этаже бросать монетку и ехать вверх/вниз, то для любого числа этажей найдется время, такое, что вероятаность невстречи меньше любого наперед заданного эпсилон.
no subject
Date: 2005-01-31 12:54 pm (UTC)Просто в силу симметрии
Ваш алгоритм дает исходя из теукщего состояния и истории (не имеет в данной задаче значения) время t через которое поменять состояние
Допустим два человека прибывает на разные этажи в один момент времени t_0
алгоритм в силу симметричности произведит одинаковые времена t_1
в t_0 + t_1 они поменяют состояния
условия (включая историю) опять симметричные и для перемены состояния оба героя произведут один и тот же t_2
и так далее
no subject
Date: 2005-01-31 12:56 pm (UTC)оба начинают кататься по этажам с интервалом минута,
но:
один катается через один этаж, а другой через два (циклически, пример для 5 этажного дома: первый приходит на первый этаж, второй на второй. для первого 1-2-3-4-5, для второго 2-4-1-3-5)
не более чем через 2Н пересекутся %))
no subject
Date: 2005-01-31 12:58 pm (UTC)иначе тривиально, конечно
(no subject)
From:(no subject)
From:(no subject)
From:(no subject)
From:во
From:Re: во
From:Re: во
From:Re: во
From:Re: во
From:Re: во
From:Re: во
From:Re: во
From:Re: во
From:Re: во
From:Re: во
From:Так у классика алгоритм уже описан :)
Date: 2005-01-31 02:55 pm (UTC)no subject
Date: 2005-01-31 04:10 pm (UTC)poterjaemsja - ona stoit na meste.
Kazhetsja uzhe pora peredogowariwat'sja :(