Spielsteineumsortierung

[Neuling]

Max hat ein Spiel, dessen Spielfeld einem Schachbrett ähnelt. 8x8 Felder, schwarz und weiß. Allerdings sind hier die Felder zeilenweise von links oben nach rechts unten von 1 bis 64 durchnummeriert. Max hatte auch mal 64 Spielsteine.
32 schwarze mit den ungeraden Ziffern 1 bis 63 und 32 weiße mit geraden Ziffern 2 bis 64.
Inzwischen sind ein paar Spielsteine verloren gegangen. Er hat nur noch 50 und weiß auch gar nicht, ob es mehr schwarze oder mehr weiße sind oder vielleicht sogar von jeder Sorte gleich viele.
Lena legt jetzt die Spielsteine willkürlich auf das Brett, aber so, dass jeder Stein auf einem Feld liegt und nicht etwa zwei oder drei Felder teilweise bedeckt. Es sind auch keine Spielsteine aufeinander gestapelt.
Max beginnt nun die Spielsteine den richtigen Feldern zuzuordnen. Bei jedem Zug setzt er einen Stein auf ein freies Feld um.
Wie viele Spielzüge sind im ungünstigsten Fall nötig?

[Cujo]

Okay, ich versuche mich mal daran...

Mehr ->

Der meiner Meinung nach ungünstigste Fall wäre, wenn es sich bei den verloren gegangenen Steinen um die Steine 51 - 64 handeln würde und die anderen Steine auf dem jeweils falschen Farbfeld wären, also z. B. die Nr. 1 auf einem weißen und die Nr. 2 auf einem schwarzen Feld (Felder 1-50). Außerdem müssten von jeder Farbe gleich viele Steine übrig sein.

Dann müsste man "rangieren". Also z. B. den Stein Nr. 1 auf Feld 60 setzen. Dann Stein Nr. 2 auf Feld 2 und Stein Nr. 1 von Feld 60 auf Feld 1. Für 2 Steine wären also 3 Züge nötig. Bei 50 Steinen wären das dann 75 Züge.

Ich bin mal gespannt, ob das so stimmt

[flinch]

Mehr ->

Also, ich denke mal, der ungünstigste Fall liegt dann vor, wenn sich immer 2 Steine gegenseitig blockieren, also Stein 1 auf Feld 2 und Stein 2 auf Feld 1, Stein 3 auf Feld 4 und Stein 4 auf Feld 3, usw. Dann braucht man für jedes dieser Paare jeweils 3 Züge, um sie auf die korrekte Position zu setzen ( 1. Zug: Stein 1 auf freies Feld, 2. Zug: Stein 2 auf jetzt freies Feld 2, 3. Zug: Stein 1 auf jetzt freies Feld 1 ). Insgesamt wären es dann 25 Paare x 3 Züge = 75 Züge

Hmm, allerdings käme es dabei überhaupt nicht auf die Aufteilung zwischen schwarzen und weißen Steinen an!?! Nochmal überlegen, ob nicht doch noch irgendwo in Haken versteckt ist...

[Neuling]

Glückwunsch an Cujo und flinch.
Ihr habt Beide die richtige Lösung genannt und auch erkannt, dass es am Ungünstigsten ist, wenn sich zwei Steine gegenseitig blockieren.

Mehr ->

Bei Cujo holpert die Überlegung etwas. Ob die Spielfläche oder die Steine schwarz oder weiß sind, spielt überhaupt keine Rolle. Auch nicht, ob Max mehr schwarze oder mehr weiße oder von jeder Sorte gleich viele Steine besitzt.
Es gibt ein Spielfeld mit 64 nummerierten Feldern und jeder noch vorhandene Spielstein kann genau einem Feld zugeordnet werden. Und ob sich zuvor ein schwarzer und ein weißer blockiert haben oder zwei von der gleichen "Farbe" ist völlig irrelevant. (Habe das Wort Farbe in Anführungszeichen gesetzt, weil ich mal - gegen mein Gefühl - lernen musste, dass weiß und schwarz keine Farben sind oder höchstens als "unbunte" Farben bezeichnet werden.)
http://de.wikipedia.org/wiki/Wei%C3%9F

Fazit: Manchmal lassen "überflüssige" Informationen ein Rätsel schwerer erscheinen, als es eigentlich ist.