Естественные науки

Кто поможет решить задачу?

Есть система тоннелей следующей структуры: кольцевой тоннель в форме окружности длиной L + отходящие на одинаковых расстояниях (равномерно по окружности кольцевого тоннеля) n проходов (n – целое неотрицательное число; n=0,1,2,…) длиной q (никакой «отходящий» проход ни с чем кроме кольцевого тоннеля не пересекается, все «отходящие» проходы одной длины). В этой системе тоннелей находится преступник и Мегрэ. Скорость передвижения Мегрэ ограничена и очень мала (в тоннелях довольно темно и он там никогда раньше не был), а скорость передвижения преступника может быть сколь угодно велика (он знает их как свои 5 пальцев). Они оба знают структуру туннелей вместе с длинами проходов. Задача Мегрэ обнаружить преступника, на котором есть «маячок». Дальность действия маячка – E (при этом он действует только по воздуху, обнаруживаться сквозь стены он не может; кривизна проходов для маячка не важна). Задача преступника не быть обнаруженным. Постарайтесь найти как можно меньшее число E, при котором Мегрэ сможет гарантированно (то есть даже в том случае, если преступник заранее знает траекторию поиска Мегрэ) поймать преступника.Формат ответа:вы должны привести дальность действия маячка - E и написать стратегию Мегамозга, при которой он сможет гарантированно поймать преступника с такой дальностью действия маячка. Критерий оптимальности:дальность действия маячка. Чем меньше, тем лучше.
Татьяна Хамова
Татьяна Хамова
588
Ну, во-первых, поскольку скорость преступника больше, чем у Мегрэ, то Мегре никогда его не поймает, если преступник по дурости не даст себя запереть в боковом корридоре. Т. е. если перступник всегда будет находиться в 10 метрах от Мегрэ и не будет заходить в боковые корридоры вперёд Мегрэ, он останется непойманным.

Поэтому я расматриваю задачу, в которой Мегрэ должен не поймать, а только обнаружить преступника.

Стратегия Мегрэ простая: идти по кольцевому корридору и по пути заходить во все боковые корридоры по порядку.

Если дальность действия маячка меньше половины длины кольцевого корридора, то преступник может держаться на противоположной от Мегрэ точке кольцевого корридора, и Мегре его никогда не обнаружит. То есть первое условие обнаружения: E > L/2.

Если боковых корридоров всего два, то этого условия достаточно. Мегрэ проверяет первый корридор, преступник прячется во втором. Когда Мегрэ выходит из первого корридора и идёт во второй, то преступник должен перебежать в первый по кольцевому корридору, но в кольцевом корридоре Мегрэ его засечёт.

Пусть корридоров три. Мегрэ проверяет первый, преступник прячется во втором. Когда Мегрэ углубляется в первый корридор на достаточное расстояние, преступник перебегает из второго в третий. Мегрэ выходит из первого и идёт во второй. Чтобы обнаружить преступника, Мегрэ должен, находясь в боковом корридоре, иметь возможность контролировать одновременно и конец бокового корридора и все выходы из корридоров (кроме противоположного, если он есть) . Значит для трёх корридоров двойной радиус действия маячка должен быть больше, чем длина бокового корридора плюс 1/3 длины кругового корридора:
2E > (q + L/3)

Аналогично:
для 4 корридоров: 2E > q + L/4
для 5 корридоров: 2E > q + 2L/5
для 6 корридоров: 2E > q + 2L/6
для 7 корридоров: 2E > q + 3L/7
для 8 корридоров: 2E > q + 3L/8

В общем виде:
для нечётных n: 2E > q + (n–1)L/2n;
для чётных n: 2E > q + (n–2)L/2n.

Одновременно должно быть
E > L/2
Игорь Змиевский
Игорь Змиевский
53 942
Лучший ответ
Мегрэ должен идти по кольцевому корридору и по очереди заходить во все боковые коридоры .

Если дальность действия маячка меньше половины длины кольцевого коридора, то преступник может держаться на противоположной от Мегрэ точке кольцевого коридора, и Мегре не сможет его обнаружить. Значит, ответ : E > L/2.
ЛС
Лариса Скр
1 102

Похожие вопросы