Policjanci i złodziej

W tym artykule zajmiemy się następującym zagadnieniem.

Policjanci gonią złodzieja w pewnej wiosce, której uliczki tworzą trójkąt równoboczny wraz z jego środkowymi (rys. 1). Maksymalna prędkość złodzieja jest $\kappa >0$ razy większa niż maksymalna prędkość policjantów. Zakładając, że wszyscy stale się widzą i ruch jest możliwy jedynie wzdłuż uliczek, należy określić, czy policjanci mogą schwytać złodzieja niezależnie od ich początkowego ustawienia.

Rozpocznijmy rozwiązanie od analizy kilku prostych przypadków. Oznaczmy liczbę policjantów przez $n.$ Załóżmy, że w wiosce znajduje się tylko jeden policjant, tj. $n=1.$ To banalny przypadek. Jeśli $\kappa <1$ (tzn. złodziej jest wolniejszy od policjanta), policjant na pewno doścignie i schwyta złodzieja. Analogicznie, jeśli $\kappa \ge 1,$ to złodziej może dowolnie długo uciekać przed policjantem, choćby biegając w cyklu $A\to B\to C\to A$ (rys. 1).

Sytuacja zmienia się diametralnie (na korzyść wymiaru sprawiedliwości), gdy w pościgu bierze udział trzech (lub więcej) policjantów. Udowodnimy, że w tym przypadku schwytają oni złodzieja niezależnie od jego prędkości. Jedna ze strategii, które do tego doprowadzą, polega na jednoczesnym zajęciu punktów $D,E$ i $F$ (oznaczenia z rys. 1). W ten sposób policjanci podzielą całą wioskę na sześć spójnych części (składowych), jak pokazano na rysunku 2. W jednej z tych części znajduje się złodziej. Na jej krańcach (podobnie jak każdej innej części) znajdują się policjanci. Wystarczy, aby jeden z nich zaczął poruszać się (w ramach tej części) w stronę drugiego, a złodziej zostanie złapany.

Pozostaje rozważyć przypadek dwóch policjantów – ten jest bardziej wymagający. Udowodnimy najpierw, że dla $\kappa \le 3$ policjanci zawsze złapią złodzieja. W tym celu jeden z policjantów będzie stale gonił rabusia – tego policjanta nazwiemy gończym. Jego jedynym zadaniem jest uniemożliwienie złodziejowi przyczajenia się na stałe w jednym miejscu. Dokładniej rzecz ujmując, musi on zadbać o to, by ostatnio odwiedzony przez złodzieja punkt środkowy zmieniał się w czasie (punktami środkowymi są punkty $D,$ $E$ lub $F$). Łatwo się przekonać, że aby to osiągnąć, wystarczy tylko jeden policjant.

Drugi policjant, którego nazwiemy stróżem, ma bardziej subtelne zadanie. Najpierw musi udać się do ,,stróżówki” znajdującej się w punkcie $S,$ który dzieli odcinek $EF$ w stosunku $1:2$ (rys. 3). Kiedy już tam dotrze, musi uważnie obserwować poczynania złodzieja. Zadaniem tego policjanta jest odcinanie drogi ucieczki złodzieja, gdy tylko jest to możliwe. Na przykład, jeśli złodziej wejdzie do ,,górnego naroża” $E\text{–}A\text{–}F$ przez punkt $E,$ stróż musi uniemożliwić mu ucieczkę przez punkt $F.$ Ma taką możliwość, gdyż $\frac{|EA|+|AF|}{|SF|}=3\ge \kappa .$ Jest też pewien mały haczyk – w tym samym momencie, w którym złodziej powróci do punktu $E,$ stróż musi ponownie znaleźć się w punkcie $S.$ Jest to jednak możliwe do zrealizowania, wystarczy, że stróż będzie poruszał się z prędkością dokładnie trzy razy mniejszą niż złodziej (z zachowaniem odpowiedniego kierunku).

Oto pełna lista możliwości stróża w zakresie kontrolowania ruchu złodzieja:

1. jeśli złodziej wchodzi do $E\text{–}A\text{–}F$ przez $E,$ nie może uciec przez $F,$

2. jeśli złodziej wchodzi do $E\text{–}A\text{–}F$ przez $F,$ nie może uciec przez $E,$

3. jeśli złodziej wchodzi do $D\text{–}B\text{–}F$ przez $D,$ nie może uciec przez $F,$

4. jeśli złodziej wchodzi do $D\text{–}C\text{–}E$ lub $D\text{–}E$ przez $D,$ nie może uciec przez $E.$

Jak już wiemy, gończy zmusza złodzieja do przechodzenia między punktami $D,$ $E$ i $F.$ Warunki (a)–(d) nakładają poważne ograniczenia na kolejność, w jakiej punkty te będą odwiedzane:

• tylko punkt $D$ może być odwiedzony bezpośrednio po $E$ lub $F,$

• tylko punkt $F$ może być odwiedzony bezpośrednio po $D,$ i to jedynie przez krawędź $D\text{–}F.$

Te ograniczenia są zilustrowane na rysunku 4. Wynika stąd, że policjanci mogą zmusić złodzieja do biegania w cyklu $D\to F\to D$! Ale jak mogą go ostatecznie schwytać? Wystarczy przekazać gończemu jeszcze jedną instrukcję: ma on poruszać się po bokach trójkąta $DFB$ tylko zgodnie z ruchem wskazówek zegara. Nie zmienia to jego zdolności do utrzymywania złodzieja w ruchu i zmuszania go do zmiany punktów środkowych, ale w ten sposób gończy w końcu go dopadnie, gdy ten zacznie już poruszać się w cyklu. To kończy uzasadnienie, że w tym przypadku policjanci mają strategię wygrywającą.

Udowodnimy teraz, że dla $\kappa >3$ to złodziej jest na wygranej pozycji (przy odpowiednim początkowym ustawieniu). Zasadniczo jego strategia polega na rozpoczęciu w jednym z punktów $D,E,F$ i przechodzeniu do innego z tych punktów za każdym razem, gdy zbliży się do niego któryś z policjantów. Spróbujmy opracować szczegóły tego podejścia.

Załóżmy, że złodziej zaczyna w węźle $D.$ Będzie tam czekał, dopóki jeden z policjantów (ponownie nazwijmy go gończym) nie zbliży się do niego na odległość mniejszą niż, powiedzmy, $\epsilon =0,2$ (zakładamy $|EF|=1$). Wtedy złodziej próbuje przejść do $E$ lub $F.$ Bez straty ogólności załóżmy, że gończy zbliża się do złodzieja ze strony punktów $B$ lub $F.$ Przyjmijmy, że złodziej pokonuje odległość $|EF|$ w minutę. Rozważmy następujące przypadki:

1. Jeśli drugi policjant uniemożliwia złodziejowi bezpośrednie przejście do $F,$ to krawędź $D\text{–}E$ jest pusta, a zatem złodziej może dotrzeć do $E$ w ciągu minuty – czyli szybciej niż każdy z policjantów (rys. 5).

2. Jeśli drugi policjant znajduje się na krawędzi $D\text{–}E,$ to złodziej może dotrzeć do $F$ w ciągu dwóch minut, zanim dotrze tam którykolwiek z policjantów (rys. 6). Zauważmy, że jeśli gończy znajduje się na odcinku $BD,$ to złodziej może dotrzeć do $F$ w ciągu zaledwie jednej minuty, ale nie ma to znaczenia dla naszej analizy.

3. W pozostałych przypadkach złodziej może bezpośrednio dotrzeć do $E$ w minutę i do $F$ maksymalnie w 2 minuty. Zauważmy, że gończy (który początkowo znajduje się blisko $D$) potrzebuje więcej niż 2 minuty, aby dotrzeć do dowolnego z tych punktów. Jeśli zaś chodzi o drugiego policjanta, rysunek 7 przedstawia dwa zbiory – jasnoniebieski to zbiór punktów, z których można dotrzeć do $E$ w minutę, a jasnozielony to zbiór punktów, z których można dotrzeć do $F$ w 2 minuty. Jasno widać, że przy założeniu $\kappa >3$ te dwa zbiory nie przecinają się. Zatem złodziej może wybrać jeden z tych punktów, mając pewność, że dotrze tam przed drugim policjantem.

Oczywiście, jeśli złodziej może raz dokonać zmiany punktu środkowego, to może tak robić w nieskończoność. Możemy więc stwierdzić, że złodziej ma strategię wygrywającą wtedy i tylko wtedy, gdy $n=1$ i $\kappa \ge 1$ lub $n=2$ i $\kappa >3.$ Rzecz jasna, problem ten można uogólnić na inne kształty wiosek, takie jak siatka $2\times 2$ czy nawet siatka $N\times M.$ Zachęcamy Czytelnika do przeanalizowania podobnych strategii dla tych przypadków.