Not logged inCSS-Forum
Forum CSS-Online Help Search Login
CSS-Shop Impressum Datenschutz
Up Topic Hauptforen / CSS-Forum / Schachrätsel
- - By Michael Bechmann Date 2013-04-24 22:57 Edited 2013-04-24 23:05
Teil 1
Ein Gefängnis sei so konstruiert, dass 64 Zellen in 8 Reihen in Nord-Süd-Richtung und 8 in jeder Reihe in West-Ost-Richtung je 8 Zellen angeordnet sind.
Die Wände sind aus Glas, denn das Gefängnis ist hochmodern. Man kann aus jeder Zelle alle anderen Zellen in die West-Ost-Richtung und in die Nord-Süd-Richtung sehen und
außerdem in alle Zellen in diagonaler Richtung.
In jeder Zelle sitzt ein Inhaftierter, außer, eine Wächterdame wird dort einquartiert (dazu später mehr). Jeder Inhaftierte möchte sich aus seiner Zelle natürlich entfernen. Auf Grund der beschriebenen Konstruktion und Anordnung kann der Häftling dies nur
über die Kanalisation (also nach unten graben) und das würde er auch sofort tun, wenn er unbeobachtet wird.

Diese Umstände kennt der Gefängnisdirektor und der hatte eine Gegenmaßnahme ersonnen: Er hatte mehrere Wächterdamen eingestellt. Diese kann man in einzelne Zellen einquartieren.
Auch eine Wächterdame sieht in waagerechte, senkrechte und diagonale Richtung und schlägt sofort Alarm, wenn sie bemerkt, dass einer der Insassen anfängt zu graben um auszubrechen.

Die Aufgabe des Direktors ist nun die:
a) Wieviele Wächterdamen muss er mindestens einstellen, damit jede Zelle beobachtet wird? Er möchte keine zuviel einstellen, denn er möchte so viel wie möglich Häftlinge
unterbringen und jede mit Wächterdamen besetzte Zelle können nicht mit Häftlingen besetzt werden.
b) In welche der Zellen muss man die Damen setzen? Gibt es mehrere Möglichkeiten?  (Die Zellen sind wie auf einem Schachbrett a1 bis h8 bezeichnet.)

Teil 2
Im nächsten Jahr wird das Gefängnis erweitert (wieder quadratisch, dann 9*9)
und später 10*10 und 11*11 Zellen.
Wieviele Damen muss man dann einstellen und in welche Zellen dann?

Teil 3
Gibt es eine allgemeine Formel um zu berechnet, wieviele Damen man in einem n*n Gefängnis einstellen muss?  
Parent - - By Werner Mueller Date 2013-04-25 10:06
Kommt ganz auf die Damen an: u.U. reicht womöglich schon eine - ansonsten https://de.wikipedia.org/wiki/Damenproblem 
Parent - - By Michael Bechmann Date 2013-04-25 11:54 Edited 2013-04-25 11:57
Die Überlegungen auf dem Link passen nicht zur Aufgabe. 
Parent - - By Werner Mueller Date 2013-04-25 13:08
[quote="Michael Bechmann"]
Die Überlegungen auf dem Link passen nicht zur Aufgabe. 
[/quote]Hmm...  ... dann bin ich ja mal gespannt.
Parent - - By Michael Bechmann Date 2013-04-25 16:45
Wenn es 8 wären, würde ich sie auf a1,b1...h1 setzen und alle 8 Linien sind überwacht. Soviele Gedanken wie in dem Link bräuchte man dann nicht. 

Eine ist wiederum zu wenig - wo sollte man die dann hinsetzen, so, dass sie alle Felder (Zellen) überwachen kann?
Parent - - By Werner Mueller Date 2013-04-25 20:17
[quote="Michael Bechmann"]
Wenn es 8 wären, würde ich sie auf a1,b1...h1 setzen und alle 8 Linien sind überwacht. Soviele Gedanken wie in dem Link bräuchte man dann nicht. 

Eine ist wiederum zu wenig - wo sollte man die dann hinsetzen, so, dass sie alle Felder (Zellen) überwachen kann?
[/quote]Das mit der einen war so zu lesen, dass allein durch das Wissen um die Anwesenheit einer solchen (besonders attraktiven) keiner mehr ausbrechen wollte.
Parent - By Michael Bechmann Date 2013-04-26 16:39
Jede einzelne der Wächterdamen sei mindestens 45 Jahre alt und wiegt mindestens 100 kg.
So eine Enttäuschung...  
Parent - - By Thomas Ficass Date 2013-04-26 13:33
Kann man so nicht sagen. Wenn man den Artikel denn bis zum Ende lesen würde , würde man dort auf ...

Andere Aufgabenstellungen
"Für ein n×n-Schachbrett bestimme die Dominanzzahl, das ist die Mindestzahl an Damen, die ausreicht, jedes Feld des Brettes zu beherrschen. Auf dem 8×8-Brett reichen 5 Damen aus."

... stoßen (das ist dann aber auch schon alles, was in der Wikipedia dazu steht).

Interessanterweise reichen auch bei einem 9*9-, 10*10- und 11*11-Brett fünf Damen aus.

Zu Teil 3:
Eine allgemeine Formel gibt es nicht, die Anzahl benötigter Damen / Wächterinnen ist in der Regel entweder
[n/2]       oder
[n/2] + 1,
wobei die eckigen Klammern hier für das Aufrunden stehen sollen, also [6/2] = 3 und [7/2] = 4.
Nur n=3 und n=11 sind Ausnahmen, da benötigt man (n-1)/2 Damen.

OK, ich geb's zu: das war ein Plagiat. Diese Erkenntnisse stammen aus einer Dissertation von Stefan Neuhaus (inzwischen wohl Dr. Stefan Neuhaus) aus dem Jahre 2009, siehe hier:

http://kups.ub.uni-koeln.de/2916/

und dann der PDF-Download (1338Kb).
Parent - By Michael Bechmann Date 2013-04-26 16:36
Für 1 und 2
Dann ist immer noch nicht klar, wo man die 5 Damen hinsetzen muss.
Da sollte man verschiedene Varianten angeben, wobei "verschieden" heißen soll, dass nicht mehrere Variante aus nur einer mit Spiegelungen oder Drehungen enstehen.
Up Topic Hauptforen / CSS-Forum / Schachrätsel

Powered by mwForum 2.29.3 © 1999-2014 Markus Wichitill