Max Home IndustryСможет ли человек пережить нападение льва двух львов? Да, если речь идет о математике, а не о настоящих львах. Это почти классическая математическая головоломка.
Первоначально проблема была поставлена известным математиком Дж. Э. Литтлвудом. Он был другом и сотрудником еще более известного математика Г. Харди.
Проблема странная, почти игровой сценарий. Возьмите игровую площадку заданной формы, возможно, с внутренними отверстиями, куда не могут пройти ни человек, ни лев, и посмотрите, сможет ли человек найти алгоритм, который навсегда избегает львов. Предполагается, что львы и человек движутся с единичной скоростью, поэтому это скорее игра с геометрической стратегией, чем с атакой.
Есть несколько вариантов этого вопроса. Например, один лев и одинокий человек на круговой арене. В этом случае известен алгоритм уклонения от льва:
Проведите линию между мужчиной и львом. Бегите под прямым углом к этой линии в течение установленного времени. Повторить.
Вы можете доказать, что независимо от того, какую стратегию использует лев, то есть какой путь он выберет, расстояние между человеком и львом положительно, и, следовательно, лев никогда не поймает человека.
Однако, если на круговой арене находятся два льва, человеку не спастись.
В случае с двумя львами и ареной любой формы с отверстиями решение не было известно до публикации недавней статьи группы исследователей из Департамента компьютерных наук Копенгагенского университета, Дания:
Мы отвечаем на следующий вопрос, восходящий к Дж. Э. Литтлвуду (1885 — 1977):
Могут ли два льва поймать человека на ограниченном участке с ректифицируемыми озерами? Предполагается, что львы и человек — это точки, движущиеся с максимальной единичной скоростью.
То, что озера поддаются восстановлению, означает, что их границы бесконечно длинные. Это требование — избегать патологических примеров, когда человек выживает вечно, потому что любой путь к львам бесконечно долог.
Мы показываем, что ответ на вопрос не всегда «да», на примере области R на плоскости, где у человека есть стратегия выживания вечно. R — многоугольная область с отверстиями, а внешняя и внутренняя границы — попарно непересекающиеся простые многоугольники.
Наша конструкция — первый по-настоящему двумерный пример, в котором человек может выжить.
Далее рассмотрим следующую игру, проводимую на всей плоскости, а не на ограниченной области:
Существует любое конечное число львов с единичной скоростью и один быстрый человек, который может бежать со скоростью 1 + ε для некоторого значения ε> 0. Всегда ли мужчина выживает? Мы отвечаем на вопрос утвердительно для любой постоянной ε> 0.
Так как же выглядит 2D-область?
В конце концов, это может быть важно, если вам когда-нибудь придется выбирать арену, на которой вы должны встретить двух голодных львов.
Что ж, это не простая форма! Но это даже сложнее, чем вы можете себе представить. Описание в статье гласит:
Регион с 11 озерами, в котором у человека есть выигрышная стратегия против двух львов. Человек и львы ограничены треугольными комнатами и узкими коридорами, которые их соединяют. Узкие коридоры соответствуют ребрам додекаэдра, а треугольные комнаты — вершинам.
Это сложно интерпретировать, пока вы не увеличите изображение:
Да, доступная часть района больше похожа на длинный извилистый коридор!
О втором результате тоже стоит задуматься. Если вас преследует стая любого размера, до тех пор, пока она конечна, вы можете избежать захвата, если сможете бежать быстрее любой из стаи. Так что, если вас преследует отряд, выберите самую быструю лошадь.
Доклад будет представлен на SoCG’17, 33-м Международном симпозиуме по вычислительной геометрии, который состоится в июле в Брисбене, Австралия.