Почему у пингвинов не мерзнут лапы? и еще 114 вопросов, которые поставят в тупик любого ученого

«Два покупателя потеряли друг друга, бродя по проходам между стеллажами в большом супермаркете. Стеллажи настолько высоки, что заглянуть поверх полок невозмож­но. Один человек хочет найти другого. Надо ли ему прекра­тить блуждать по залу - лучше остаться на единствен­ном видном месте, пока другой ходит по проходам? Или они быстрее найдут друг друга, если будут вместе двигаться между стеллажами?»

Дэвид Кафкевиц

Ньюарк, Нью-Джерси, США

Наилучшая стратегия — ждать у выхода из магазина на случай, если спутник наконец решит, что вы ушли до­мой или еще куда-нибудь. Максимальное время ожида­ния — от момента, когда вы потеряли друг друга, и до за­крытия магазина.

Стратегия ожидания в зале работает лишь в том случае, если один человек не сходит с места. Если на месте решите оставаться вы оба, тогда ожидание затянется до бесконеч­ности или до закрытия магазина.

Если один человек стоит на месте, а другой ищет его, тогда ему понадобится столько времени, сколько нуж­но для осмотра всего магазина. Оно во многом зависит от плана магазина: если все проходы видны с одного на­блюдательного пункта, тогда поиски упрощаются. По­добную проблему решают при проектировании тюрем, где надзиратели должны видеть как можно больше ко­ридоров сразу, или при строительстве крепостей, где защитники должны иметь максимальное прикрытие. Чтобы потерявшегося в магазине человека быстрее за­метили, он должен стоять неподвижно на пересечении проходов.

При поисках наугад оба человека будут удаляться от на­чальной точки со скоростью, пропорциональной квадрат­ному корню из времени. Зона поисков каждого из них бу­дет представлять круг с центром в начальной точке. Если эти круги имеют значительную область пересечения, про­должительность поисков будет как минимум пропорци­ональна квадрату начального расстояния, разделяющего их. Если часть проходов между стеллажами во время по­исков окажется блокированной, тогда скорость движения сократится и перед одним из потерявшихся встанет задача выйти в ту часть зала, где скорость пропорциональна не­коему дробному показателю.

Стивен Мэсси Сент-Олбенс, Хартфордшир, Великобритания

Чтобы ответить на этот вопрос, надо сначала знать, согла­совали ли эти люди заранее свои действия на случай, если они потеряются, — например, кто должен ждать, а кто вес­ти поиски. Если они договорились вести поиски самосто­ятельно, проблема представляет собой асимметричный вариант проблемы со встречей (см. ниже), в противном случае это симметричный вариант.

Оба варианта проблемы рассматриваются в статье, ко­торая будет опубликована в «Журнале управления и опти­мизации Общества промышленной и прикладной матема­тики» (Society for Industrial and Applied Mathematics Journal of Control and Optimization), в ней же анализируются некото­рые специфические ситуации в конкретных районах поис­ков. Во всех случаях, когда были получены точные решения (с наименьшим ожидаемым или оптимальным временем), оба человека двигались все время с максимальной скоро­стью. При этом потерявшийся не должен останавливаться, пока второй продолжает поиски. Например, в упрощенной модели, в которой два человека разделены одним отделом, но ни один не знает, куда движется другой, тому, который ищет, понадобится время, равное (1 + 3):2 = 2, чтобы найти того, который стоит на месте (при условии нулевой види­мости). Но при оптимальном движении это время можно сократить до 13/8.

Единственный известный мне случай, оптимальный для ищущего и для ждущего, — когда два человека произ­вольно размещены в пределах одного круга, и этот случай будет оптимальным лишь в отсутствие общего движения по часовой стрелке; наилучший вариант — когда один дви­жется по часовой стрелке, другой — против.

Все эти результаты и вопросы подразумевают, что искатели найдут друг друга, только когда они сойдутся или окажутся в зоне слышимости. Ситуация применима к многолюдному супермаркету, когда видимость в про­ходах ограничена. Насколько мне известно, ситуацию с возможностью видеть вдаль по проходам никто не мо­делировал.