Wandern in drei Korridoren • Konstantin Knoop • Populäre wissenschaftliche Aufgaben zu "Elementen" • Mathematik

Wandern Sie in drei Gängen

Aufgabe

Drei gerade Gänge von gleicher Länge d Bilden Sie die in Abbildung 1 abgebildete Figur.

Abb. 1.

Der Gangster und der Polizist bewegen sich durch die Korridore und die Höchstgeschwindigkeit des Polizisten ist 2 mal höher als die Höchstgeschwindigkeit des Gangsters. Leider sind die Korridore lang und der Polizist hat eine begrenzte Sichtweite – er wird den Gangster nur dann sehen können, wenn er nicht mehr als 1 Meter entfernt ist.

Komm mit Ein Algorithmus, mit dem ein Polizist einen Gangster fangen kann: a) an d = 3; b) an d = 4,999; c) überhaupt d < 7.


Tipp 1

Der Polizistalgorithmus sollte nicht davon abhängen, was und wie der Gangster macht, denn der Polizist sieht den Gangster nicht im Prozess der Ausführung des Algorithmus (und in diesem Moment, wenn er sieht, wird der Gangster erwischt, weil der Polizist einen Geschwindigkeitsvorteil hat). Insbesondere sollte der korrekte Algorithmus mit jedem Verhalten des Gangsters funktionieren, und selbst wenn der Gangster weiß, wo sich der Polizist zu jeder Zeit befindet. In der Tat müssen wir die "Verfolgungsjagd" finden, die es der Polizei ermöglicht, den Gangster im "Kleeblatt" zu finden.Wir können also davon ausgehen, dass sich der Polizist entlang dieser Kurve immer so schnell wie möglich bewegt.


Tipp 2

Lass den Cop von Punkt zu Punkt fliegen A in die Mitte des Kleeblatts Ogeht dann ein Stück weit den Korridor entlang OB und kommt zurück zu O (Abb. 2). Wie weit kann er gehen, so dass er im Moment seiner Rückkehr sicher sein muss, dass kein Gangster auf dem Gang ist Oa?

Abb. 2


Tipp 3

Die Antwort auf die in Tipp 2 formulierte Frage ist 2. Daher Absatz a) schon gelöst: Es gibt keinen Gangster im Gang Oanoch im Gang OBdeshalb muss er im Korridor sein OCund genau da fängt sein Polizist weiter an.

Um den Artikel zu lösen b) Der Polizist muss weiter jagen – zuerst in den Korridor gehen OC eine Entfernung, so dass zum Zeitpunkt der Rückkehr genau verstanden wird, dass der Gangster keine Zeit hatte, darüber zu rennen OB in der Oa. (Beweisen Sie, dass dieser Abstand gleich 3 ist.) Wenn er zurückkehrt, kämmt er wieder. OB so dass der Gangster zum Zeitpunkt der Rückkehr keine Zeit hatte, ihm zu begegnen OC in der Oa. Und so weiter – finde heraus, warum dies für irgendeinen Wert ausreicht. dweniger als 5.

Abb. 3


Lösung

a) Also warum, wenn d = 3 ist wahr was im zweiten Hinweis steht? Das ist warum, nachdem der Polizist "in den Korridor" "getaucht" hat OB bis zu einer Tiefe von 2 und zurück zu O es kann argumentiert werden, dass der Gangster genau in OC? Es ist klar, dass er nicht im Korridor ist OBweil, vorbeigegangen OB die Entfernung d – 1 = 2, der Polizist sah das Ende des Korridors. Konnte der Gangster in dieser Zeit Zeit haben, aus dem Gang zu springen? OC in den Korridor Oa und dort in der Entfernung sein, wo es von einem Punkt ist O Wird der Polizist nicht sehen? Nein, denn zuerst war er auf dem Flur> 1 OCAm Ende sollte auf dem Flur> 1 sein Oa, was bedeutet, dass es mehr als 2 passieren muss. Während der Polizist jedoch im Korridor ging OB, ein Gangster konnte nicht mehr als die Hälfte des Weges eines Polizisten zurücklegen, also (2 + 2) / 2 = 2. Punkt a) aufgelöst.

b) Jetzt wollen wir uns mit dem Fall befassen d = 4.999. In Abb. 3 zeigt die Position des Polizisten nach dem "Tauchen" in den Korridor. OC in einer Tiefe von 3. Zurück zu einem Punkt O und den Gangster nicht zu sehen, weiß der Polizist das auf dem Gang OC der Gangster war nicht mindestens so tief wie 4. Außerdem konnte der Gangster unbemerkt den Gang nicht überqueren OB in den Korridor Oa, weil er dafür eine Distanz von mehr als 4 brauchte, während der Polizist 2 + 3 + 3 = 8 passierte, und das ist mit seiner Geschwindigkeit unmöglich.

Bitte beachten Sie, dass der zweite "Tauchgang" vom Polizisten bis zu einer Tiefe von 3 gemacht wurde, weil (2 + 3 + 3) / 2 <2 + 1 + 1. Wie berechnet man die Tauchtiefe des nächsten Polizisten (wieder in den Korridor OB) Er kann es sich leisten, dorthin zu gehen x und zurück, wenn der Gangster während dieser Zeit keine Zeit hat, aus dem Korridor zu springen OC und vertiefen sich in Oa eine Entfernung größer als 1. Da der Polizist ist sicher, dass im Flur OC es gibt keinen Gangster mindestens bis zu einer Entfernung von 3 + 1 = 4, dann die Bedingung (3 + x + x) / 2 <4 + 1, d.h. x <3.5. Nach oben gehen x = 3,5 zum Korridor OBDer Polizist weiß bereits, dass in diesem Korridor der Gangster nicht weit entfernt ist x + 1 = 4,5, also die Tiefe y der nächste Gang tauchen OC kann so sein, dass die Ungleichung gilt (3,5 + y + y) / 2 <4,5 + 1, d.h. y < 3,75.

Wir sehen, dass die "Tiefen des Eintauchens" eines Polizisten (abwechselnd in die Korridore) OB und OC) Bilden Sie eine Sequenz von 2, 3, 3,5, 3,75. Können wir eine Formel angeben, die die Mitglieder dieser Sequenz definiert? Natürlich. Wenn eingeschaltet nIn einem Schritt betrat ein Polizist einen der Korridore in einiger Entfernung a(n), dann ist kein Gangster in diesem Korridor bis zur Entfernung a(n) + 1, was bedeutet, dass das Eintauchen des nächsten Polizisten in den nächsten Korridor eine solche Tiefe haben kann a(n + 1) zu

(a(n) + a(n + 1) + a(n + 1))/2 ≤ a(n) + 2.

Wo bekommen wir das? a(n + 1) = (a(n) + 4) / 2. Diese Rekursionsbeziehung kann leicht in eine explizite Formel für umgewandelt werden nth Mitglied der Sequenz: Es zeigt an, dass jeder nächste Punkt das Segment zwischen dem vorherigen Punkt und Punkt 4 halbiert. Mit anderen Worten, jeder nächste Punkt ist doppelt so nah an 4 wie der vorherige Punkt. Das bedeutet aber, dass die Entfernung zu 4 (die zu Beginn 2 war) bei jedem folgenden Tauchgang um das Zweifache verkürzt wird, also um 4 – a(n) = (4 − a(0))/2n. Vereinfachung dieser Gleichung erhalten wir 4 – a(n) = 2/2n, a(n) = 4 − 2/2n. Es ist klar, dass von einigen ausgehend n Bedeutung a(n) wird mehr als 3.999 sein, was bedeutet, dass es ausreichen wird, den Gangster aus dem Korridor der Länge vollständig zu verdrängen d = 4,999.

c) Und jetzt der interessanteste Moment. Jagen Sie die Korridore OB und OC Wie Sie oben gesehen haben, können Sie mit Korridoren jeder Länge von weniger als 5 umgehen. Aber wie löst man das Problem für längere Korridore?

Hier kommt uns eine Gelegenheit, die wir noch nicht genutzt haben, zu Hilfe: Den Gangster weit genug vom Punkt weggetrieben Okann ein Polizist einen der Korridore bis zum Ende durchkämmen (zur Bestimmtheit den Korridor) OB er wird vom Polizisten zu dem Punkt geführt, von dem er das Ende des Korridors sehen wird). Ja, während der Gangster aus dem Korridor springen kann. OC in der Oa durch Punkt Oaber er wird nicht in der Lage sein, den Flur zu verlassen Oa sehr weit! Passiere dann den Korridor Oa In der erforderlichen Tiefe wird der Polizist sicher sein, dass der Gangster nicht da ist. Was ist, wenn der Gangster Zeit hat, umzuziehen? OC wieder in OB? Ja, lass ihn Zeit haben, wenn er es nur schafft, zur Seite zu gehen OB offensichtlich weniger als es möglich wäre, hineinzutauchen Oa im vorherigen Schritt. Wenn wir sehen, dass solch eine Abfolge von Tauchgängen für den Gangster auf 0 reduziert wird, bedeutet dies, dass der Polizist früher oder später garantieren kann, dass es im nächsten Gang keinen Gangster gibt, und dann hat der Gangster den einzigen Korridor, wo er gefangen wird.

Alles, was uns noch bleibt, ist, all diese "Tauchgänge" sorgfältig zu zählen.

Lassen Sie die Entfernung, die der Polizist in den Korridor gegangen ist OC vor dem Kämmen bis zum Ende des Korridors OBgleich c. Seitdem im Korridor OB Der Polizist ging hin und her d – 1, dann während dieser Zeit hat der Gangster nicht mehr passiert d – 1 + c / 2. Und seit er aus war O nicht näher als c + 1, dann geh tief hinein Oa Er kann nicht mehr als a = d − 2 − c/ 2. Um sicherzustellen, dass der Gangster nicht wirklich in Oamuss der Polizist diesen Korridor in einer Tiefe von 2 (a – 1). (In der Tat wird der Gangster während dieser Zeit nicht mehr als passieren können a – 1, was bedeutet, dass es nicht weiter als 2 ista – 1 von Punkt ODas heißt, nicht weiter als 1 Meter vom Polizisten entfernt, und wird entdeckt und gefangen.) Wenn der Polizist diese Gangkontrolle beginnt Oader Gangster ist in OC nicht näher als 1 weg O. Daher am Ende der Kontrolle (wenn der Polizist zurückkehrt) O) kann der Gangster in den Korridor rennen OB nicht weiter als die Entfernung b = 2a – 3. Bedingung "b < a"Was wir erreichen wollten, entspricht der Ungleichheit 2a − 3 < adas ist das a <3. Daher die Notwendigkeit dc/2 < 5, d < 5 + c/ 2. Seit dem Wert c kann dann beliebig nahe 4 gemacht werden d kann beliebig nahe 7 gemacht werden.


Nachwort

Die Aufgabe, einen Polizisten und einen Gangster zu verfolgen, gehört zu einer Reihe von Aufgaben Garantierte Suche (siehe Verfolgung-Umgehung). Zum ersten Mal wurden solche Probleme 1978 vom Amerikaner Torrens Parsons (Torrence Parsons) in Betracht gezogen. Der ursprüngliche Plot des Problems, den Parsons gelöst hatte, war verwandt mit der Suche nach einem Mann, der in einer dunklen Höhle verloren gegangen war. Es wurde angenommen, dass derjenige, der nach ihm sucht, einen Umweg über die Grafik macht und die vermisste Person findet, falls er sich in der Ecke neben ihm befindet.

Einige Jahre später, 1982, wurde die Arbeit von P. A. aus Leningrad veröffentlicht.Golovach, in dem die ε-Suche zuerst betrachtet wurde, das heißt, anstatt den Graphen zu durchlaufen, wurde ein Pfad auf geometrischen Objekten betrachtet, und die Bedingung für den Erfolg (Objekterkennung) wurde formuliert, um einen Abstand ε zu erreichen. In einer solchen Formulierung war es bereits offensichtlich, dass das gesuchte Objekt dem Nachweis widerstehen konnte und die Aufgabe ist herauszufinden, in welchen Fällen dieser Widerstand erfolgreich sein kann.

Es sollte angemerkt werden, dass sowohl Parsons als auch Golovach ein etwas anderes Problem lösten – sie suchten nach dem Mindestwert der Anzahl der Verfolger, die den Erfolg der Eroberung garantieren würden (mit jeglicher Untätigkeit oder Opposition). Und die Aufgabe eines Polizisten und eines Gangsters erschien streng zwischen der Veröffentlichung der Werke von Parsons und Golovach und an einem sehr unerwarteten Ort – bei der Moskauer Mathematischen Olympiade, in Optionen für 9 und 10 Klassen. Es ist nicht ganz klar, ob die Autoren des Problems damals von einer allgemeineren Formulierung wussten oder ob dies ein Zufall war.

Im Laufe der Jahre hat die Aufgabe eine Vielzahl von Optionen und Generalisierungen erhalten. Also, die kommentierte Bibliographie zu diesem Thema, veröffentlicht 2008 in einer Sonderausgabe der Zeitschrift Theoretische Informatik, enthält 172 Positionen, und im Jahr 2011 gab es sogar eine separate Schulung für Studenten – "Das Spiel der Cops und Räuber auf Graphen".


Like this post? Please share to your friends:
Schreibe einen Kommentar

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: