Museumswächterproblem: Unterschied zwischen den Versionen
LasseB (Diskussion | Beiträge) |
LasseB (Diskussion | Beiträge) |
||
| Zeile 2: | Zeile 2: | ||
== Museum-Ritter == | == Museum-Ritter == | ||
| − | Zuerst betrachten betrachten wir das [https://www.museum-ritter.de/de/inhalt/home.html Museum-Ritter], welches zum gleichnamigen Schokoladenhersteller gehört. Natürlich ist der Grundriss perfekt quadratisch. Der Museumsdirektor möchte nun Museumswächter einstellen und fragt sich, wie viele Leute er anstellen muss, wenn ein Wächter sich zwar nicht frei im Raum bewegen, aber sich um seine Achse drehen darf. Diese Frage ist trivial, es reicht ein Wächter, irgendwo im Raum positioniert. Wie sieht es aber aus, wenn das Museum einen etwas komplizierteren Grundriss besitzt? | + | Zuerst betrachten betrachten wir das [https://www.museum-ritter.de/de/inhalt/home.html Museum-Ritter], welches zum gleichnamigen Schokoladenhersteller gehört. Natürlich ist der Grundriss in unserer idealisierten Mathewelt perfekt quadratisch. Der Museumsdirektor möchte nun Museumswächter einstellen und fragt sich, wie viele Leute er anstellen muss, wenn ein Wächter sich zwar nicht frei im Raum bewegen, aber sich um seine Achse drehen darf. Diese Frage ist trivial, es reicht ein Wächter, irgendwo im Raum positioniert. Wie sieht es aber aus, wenn das Museum einen etwas komplizierteren Grundriss besitzt? |
== Satz == | == Satz == | ||
| Zeile 10: | Zeile 10: | ||
== Beweis nach Steve Fisk == | == Beweis nach Steve Fisk == | ||
| − | Für ein Museum mit <math>n=3</math> Ecken ist die Anzahl der Wächter klar. Für ein Museum mit <math>n>3</math> Wänden beschreiben wir den Grundriss als Polygon. Wir verbinden alle Ecken mit <math>n-3</math> sich nicht kreuzenden Linien <span style="color:#EE0000"> Hier wäre eine Skizze eines triangulierten Polygons gut </span>. | + | Für ein Museum mit <math>n=3</math> Ecken ist die Anzahl der Wächter klar. Für ein Museum mit <math>n>3</math> Wänden beschreiben wir den Grundriss als Polygon. Wir verbinden alle Ecken mit <math>n-3</math> sich nicht kreuzenden Linien <span style="color:#EE0000"> Hier wäre eine Skizze eines triangulierten Polygons gut </span>. Um nun die Anzahl der benötigten Wächter zu bestimmen, Färben wir alle Ecken der Dreiecke in drei verschiedenen Farben ein, wir nehmen o.B.d.A die Farben <span style="color:#FF0000"> rot</span>, <span style="color:#0000FF">blau</span> und <span style="color:#FFA500"> orange </span> |
=== Definition: Polygon=== | === Definition: Polygon=== | ||
Ein Polygon ist ein Tupel <math>P=: \left(P_1,P_2,\dots,P_n \right)</math>, von n verschiedenen Punkten <math>P_i,\ 1\leq i\leq n,\ n\in\mathbb{N}</math>. Dabei heißen die n Punkte Eckpunkte des Polygons (man spricht auch von einem n-Eck) und die Strecken zwischen den | Ein Polygon ist ein Tupel <math>P=: \left(P_1,P_2,\dots,P_n \right)</math>, von n verschiedenen Punkten <math>P_i,\ 1\leq i\leq n,\ n\in\mathbb{N}</math>. Dabei heißen die n Punkte Eckpunkte des Polygons (man spricht auch von einem n-Eck) und die Strecken zwischen den | ||
Version vom 19. März 2021, 14:44 Uhr
Das Museum ist wegen Corona geschlossen, deswegen werden keine Wächter benötigt:-(
Museum-Ritter
Zuerst betrachten betrachten wir das Museum-Ritter, welches zum gleichnamigen Schokoladenhersteller gehört. Natürlich ist der Grundriss in unserer idealisierten Mathewelt perfekt quadratisch. Der Museumsdirektor möchte nun Museumswächter einstellen und fragt sich, wie viele Leute er anstellen muss, wenn ein Wächter sich zwar nicht frei im Raum bewegen, aber sich um seine Achse drehen darf. Diese Frage ist trivial, es reicht ein Wächter, irgendwo im Raum positioniert. Wie sieht es aber aus, wenn das Museum einen etwas komplizierteren Grundriss besitzt?
Satz
Nun betrachten wir ein Museum mit einem beliebigen Grundriss, welcher allerdings komplexer ist als der Grundriss des Museum-Ritter. Einzige Voraussetzung ist, dass sich alle Wände durch eine Gerade beschreiben lassen. Nun möchte unser Museumsdirektor wieder Wächter einstellen und fragt sich, wie viele er braucht, damit diese das komplette Museum im Blick haben. Auch hier gilt wieder, dass sich die Wächter nicht hin und her bewegen, sondern auf ihren Plätzen bleiben und sich nur um ihre Achse drehen können. Dann benötigt man folgende Anzahl an Wächtern:
Für jedes Museum mit [math]n[/math] Wänden reichen [math]\lfloor \frac{n}{3} \rfloor[/math] Wächter aus.
Beweis nach Steve Fisk
Für ein Museum mit [math]n=3[/math] Ecken ist die Anzahl der Wächter klar. Für ein Museum mit [math]n\gt 3[/math] Wänden beschreiben wir den Grundriss als Polygon. Wir verbinden alle Ecken mit [math]n-3[/math] sich nicht kreuzenden Linien Hier wäre eine Skizze eines triangulierten Polygons gut . Um nun die Anzahl der benötigten Wächter zu bestimmen, Färben wir alle Ecken der Dreiecke in drei verschiedenen Farben ein, wir nehmen o.B.d.A die Farben rot, blau und orange
Definition: Polygon
Ein Polygon ist ein Tupel [math]P=: \left(P_1,P_2,\dots,P_n \right)[/math], von n verschiedenen Punkten [math]P_i,\ 1\leq i\leq n,\ n\in\mathbb{N}[/math]. Dabei heißen die n Punkte Eckpunkte des Polygons (man spricht auch von einem n-Eck) und die Strecken zwischen den