Die Aufgabe des Monats März

In Museen gibt es immer ein Problem, das Problem der Aufsicht. Jeder Winkel muss ständig überwacht werden, deshalb braucht man viele Wärter. Aber schon aus Kostengründen möchte man mit möglichst wenig Aufsehern auskommen. Das Problem lautet also:

Welche Zahl von Wärtern braucht man, um ein beliebig geformtes Museum lückenlos überwachen zu können ?

Man macht dabei folgende (vereinfachende) Annahmen:

• Das Museum fülle nur eine Ebene aus. Es ist also nicht auf mehrere Etagen oder Gebäude verteilt.
• Ansonsten gibt es keine Einschränkungen für die Architektur.
• Das Museum besteht also aus dem Innern eines beliebigen Vielecks.

Es ist überhaupt nicht klar, ob es eine plausible Antwort auf die Frage gibt. Wenn überhaupt, dann hängt sie von der Anzahl n der Ecken ab. Je mehr Ecken und Kanten das Museum hat, desto mehr Aufseher benötigt man.

Schaffst Du es, das Problem zu lösen? Die beste Lösung wird prämiert!

Lösungen bis zum 31.03.11 an THI.