Экшн на тессеракте

[Ian]

Дан тессеракт (4мерный куб), Два полицейских и вор могут стоять только в его вершинах , а за один ход перебежать по одномерному ребру в любую из соседних вершин, либо простоять на месте. Сначала полицейские выбирают себе вершины, потом вор. Потом ходят полицейские, потом вор... Все друг друга видят. Вор пойман, если он оказался в какой-то момент в одной вершине с полицейским.
1. Доказать, что вор сумеет убегать бесконечно долго.
2. Придумать граф не с 16 вершинами, а меньше, в котором тоже вор сможет убежать от двух полицейских.

[zykov]

Source of the post Сначала полицейские выбирают себе вершины, потом вор

Вор знает, что они выбрали или не знает?

[Ian]

Да видит, чтобы не встать на битую вершину, конечно

[peregoudov]

Начну по-простому. Положение каждого участника можно охарактеризовать 4-значным двоичным числом. Перебежка --- изменение одного из битов этого числа.

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

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

P. S. Ах, да! Надо еще доказать, что вор всегда может выбрать начальное положение не менее чем в двух перебежках от полицейских. В двух перебежках от первого полицейского расположены 6 вершин. По крайней мере две из них расположены не менее чем в двух перебежках от второго. Одну из них и может выбрать вор.

[Ian]

Согласен, у меня так же

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

А эту ситуацию я назвал"один преследует, второй в засаде"(в противоположной от вора вершине квадрата)
Для анализа задачи 2 учтем, что в тессеракте 1) все вершины имели одинаковую степень 4 2) и вообще они эквивалентны друг другу, т.е. существует изоморфизм графа на себя, что данная вершина переходит в данную 3) нет циклов длины 3 -значит, полицейский не может угрожать и вору, и месту, куда он может отойти. Эти свойства и позволили доказать стратегию вора.

[peregoudov]

Так вы хотите сказать, что можно придумать граф, удовлетворяющий всем вашим трем условиям, и содержащий менее 16 вершин? Или какое-то условие надо ослабить? Нет, силой мысли я такое решить не могу: у меня совсем нет опыта размышлений о графах.

[Ian]

Да вот один нашелся (уже после открытия этой темы), все циклы длины не меньше 5, а степень всех 10 вершин равна 3. Он назван чьим-то именем, но не могу найти учебник, в котором его видел. Та же пассивная тактика -убегать только при наличии угрозы.

k10.png (5.07 KiB) 18970 просмотра

[Ian]

3. Граф, на котором вор сможет убежать от трех полицейских.
У меня получился с 25 вершинами

[Ian]

Типа тессеракта, но все грани-пятиугольники. В нем трое не могут поймать вора

5x5.png (21.49 KiB) 18745 просмотра

[peregoudov]

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

[Ian]

Последний граф построен так. Не должно быть циклов длины меньше 5 (чтобы ни один коп не мог контролировать два пути отхода вора) Все вершины должны иметь степень 4(если меньше, эту вершину три копа могут окружить, а мы хотим, чтобы даже теоретически ни одной матовой позиции не существовало.А если больше, тоже ничего хорошего, копы предпочтут занять эту вершину и нам же хуже).
Поэтому стартуем от пятиугольника, и наверняка есть непересекающийся с ним пятиугольник(на рисунке жирные). Если мы свяжем их ребрами, получится как бы отображение множества вершин одного пятиугольника на вершины другого. Чтобы при этом не образовалось циклов длины 4, надо, чтобы выполнялось свойство - вершины, соседние в образе этого отображения, не должны быть образами соседних. Такое биективное отображение (= перестановка) существует (14253). Вот я и соединил соседние пятиугольники согласно этой перестановке. Легко доказать, что циклов длины 4 там нет, Нет циклов, проходящих через 3 жирных пятиугольника, потому что ребра проведены по биекции. И нет циклов, проходящих через 2 жирных пятиугольника, по свойству выбранной перестановки.