Serie-12

Beitragsseiten

Seite 5 von 13

Aufgabe 5

Bernd und Mike kamen bei ihrer Skiwanderung beim Bernds Opa vorbei. Der saß vor einem Spielbrett, welches aus einer Reihe von Quadraten bestand und zwar genau 10. Auf diesem lagen vier rote und und vier blaue Spielsteine nebeneinander und zwar abwechselnd, die beiden linken Felder waren frei. Was ist denn für ein Spiel fragten die beiden wie aus einem Mund.

++RBRBRBRB

Nun, es sollen die Steine so sortiert werden, dass es am Ende so aussieht. Alle blauen Steine links, daneben alle roten und die beiden Felder rechts sind frei.
BBBBRRRR++

Die Steine dürfen nur auf eine Art bewegt werden.
Spielzug: Es werden zwei benachbarte Steine in die Hand genommen und auf zwei freie Felder wieder abgelegt. Dabei darf aber der linke Stein nicht mit dem rechten Stein vertauscht werden.
In Gedanken waren Mike und Bernd schon am Sortieren, da meinte der Opa noch, dass es mit nur vier Spielzügen gelingen muss. Ups, das ist nicht gerade einfach, oder?
Zu erreichen sind 8 Punkte.

Lösung

Hier die schnellste Antwort der Kinder von Andree, vielen Dank.
+ + R B R B R B R B wird zu (1. Zug)
B R R B R B R + + B wird zu (2. Zug)
B R R B + + R R B B wird zu (3. Zug)
B + + B R R R R B B wird zu (4. Zug)
B B B B R R R R + +
Interessanterweise, haben alle Teilnehmer nur diese Variante gefunden, gibt es also nur die?
Wer probieren will, der kann auch das noch das probieren:
+ + R B R B R B R B R B in 5 Aktionen sortieren
...
++(RB)n, d.h. n Paare mit n > 3 lassen sich immer mit n Aktionen umsortieren.
(Beweisidee: Man zeigt, das es für n=4, n=5; n=6 und n=7 geht. Dann mit vollständiger Induktion:
Induktionsannahme: Es wird angenommen, für n-4 Paare gilt, dass die Aufgabe mit n-4 Aktionen erfüllbar ist.
Dann ist zu beweisen, dass für n Paare 4 Aktionen mehr notwendig sind als für n-4 Paare