Spielsteinumsortierung 2

[Otmar]

Nachdem Neuling neulich Speilsteine sortiert hat, ist mir dazu auch was eingefallen:

Auf einem quadratischen Spielbrett mit 10 Zeilen und 10 Spalten, gibt es 100 Felder. Spalten und Zeilen sind jeweils von 0 bis 9 durchnummeriert. Dazu gibt es 100 Spielsteine mit aufgedruckten Zahlen z von 0 bis 99. Max legt die Steine auf das Spielbrett. Bei jedem Stein multipliziert er die darauf stehende Zahl z mit 3 und erhält eine neue Zahl d = 3*z. Die Einerstelle von d ist die Spalte und die Zehnerstelle von d ist die Zeile des Feldes auf das Max den Spielstein hinlegt. Nachdem Max fertig ist, darf Lena die Steine umlegen. Bei jedem Zug werden von ihr zwei Spielsteine vertauscht. Wieviel Züge muss Lena mindestens machen, dass alle Steine in der Spalte der Einerstelle von z und der Zeile der Zehnerstelle von z liegen?

Bei einstelligen Zahlen z oder d wird als Zehnerstelle natürlich 0 angenommen.

[Neuling]

Mein 1. Gebot wären

Mehr ->

89 Tauschaktionen

wegen

Mehr ->

4 Ringe a 20 Steine ----> 76 Aktionen
4 Ringe a 4 Steine ------> 12 Aktionen
1 Ring a 2 Steine ---------> 1 Aktion
2 Steine schon richtig

Bitte längere Spoilersperre

[Otmar]

@Neuling,
super schnell und vollkommen richtig gelöst!

Meine Lösung:

Mehr ->

Was macht Max? Er legt 100 nummerierte Spielsteine als Permutation auf 100 Felder, wobei die Felder die Nummer 10*Zeile + Spalte haben. Da 3 und 100 teilerfremd sind, wird auch kein Feld doppelt belegt. Lena soll die Permutation mit Vertauschungen (Transpositionen) rückgängig machen. Ähnlich wie beim ersten Rätsel dieser Art ist für die minimale Zuganzahl wichtig, was sich gegenseitig blockiert. ZB liegt Stein 25 auf Feld 75 und Stein 75 auf Feld 25. Geschrieben wird das bei einer Permutation als Zyklus (25 75). Ein weiterer Zyklus ist z.B.: (5 15 45 35). Das entspricht der Belegung:

Feld   5	15	45	35
Stein 15	45	35	5

Wenn Lena den Stein 5 jetzt durch drei Vertauschungen über Feld 45 15 nach Feld 5 tauscht, ist sie mit diesem Zyklus fertig. So kann sie für jeden Zyklus vorgehen und es ist das Optimum was Lena machen kann. Sie braucht für jeden Zyklus mit n Steinen n-1 Vertauschungen, um ihn zurückzutauschen. Auch beim Sonderfall n=1 z.B. für Feld 0 gilt diese Regel, denn für so einen Zyklus muss sie gar nicht tauschen.
Da bei jedem Zyklus einmal weniger getauscht wird, als dieser Steine hat, ist sie bei m Zyklen nach 100-m Zügen fertig.
Jetzt brauchen wir die Anzahl der Zyklen (a0 a1 …). Es gilt (alles modulo 100)
a(k+1) = 3 a(k)
a(k) = 3^k a(0)
Fangen wir mit Feld a(0) = 1 an.
1->3->9->27->81---->61---->41---->21---->1
->: *3 Sprung um ein Element des Zyklus
---->: *81 Sprung um vier Elemente des Zyklus
Ab 81 können wir jeweils 4 Elemente weiterspringen, da in den übersprungenen Elementen die letzte Ziffer nicht 1 sein kann. Dieser Zyklus hat also genau 20 Elemente. Wegen a(k) = 3^k a(0) kann nun kein anderer Zyklus mehr als 20 Elemente haben und die Zahl der Elemente muss ein Teiler von 20 sein.
Die Elemente mit Endziffer 0 bzw. 5 bleiben unter sich und liefern die 7 Zyklen:
(0), (10 30 90 70), (20 60 80 40), (50), (5 15 45 35), (25 75), (55 65 95 85)
Die Teiler von 20 sind 1, 2, 4, 5, 10 und 20. Wenn ein Zyklus weniger als 20 Elemente hat, muss also entweder gelten a(10) = a(0) oder a(4) = a(0) also entweder 3^10 a(0) = a(0) oder 3^4 a(0) = a (0). Da 3^10 = 49 ist, soll a(0) = 49 a(0) sein. Das geht bei keiner der verbliebenen Endziffern (1,2,3,4,6,7,8,9) da keine übrige Endziffer nach Multiplikation mit 9 die gleiche Endziffer hat. Für 3^4=81 sei a(0) = 10z + e mit der Zehnerziffer z und der Einerziffer e. Dann folgt aus 81 a(0) = a(0)
810z+81e = 10z+e
10z + 81e = 10z+e
81e = e
80e = 0
Auch die letzte Gleichung gilt nicht für die verbliebenen Endziffern. Also haben alle anderen Zyklen 20 Elemente. Da noch 80 Felder übrig waren, sind das noch 4 weitere Zyklen. Damit hat die Permutation von Max genau 11 Zyklen und Lena muss mindestens 100 - 11 = 89 Züge machen.

[Neuling]

@ Otmar
Man bin ich froh, dass ich die Aufgabe lösen konnte, bevor ich Deine Erklärung gelesen habe. Das mag zwar alles mathematisch korrekt sein, aber versteht das ein "Laie"?

Max und Lena wissen,

Mehr ->

dass Spielsteine paarweise vertauscht werden können oder 3 oder 4 oder ... alle miteinander. Sie haben sich über drei, dann vier, dann fünf Steine usw. erschlossen, dass für n miteinander vertauschte Steine (n-1) Züge nötig sind, die Steine wieder auf die richtigen Positionen zu bringen. Lena würde es so erklären:
Stelle dir 10 Steine vor, die so vertauscht sind, dass sie eine Kette bilden -
10, 1, 2, 3, 4, 5, 6, 7, 8, 9
Dann lasse die 10 wandern, bei jedem Zug um eine Stelle nach rechts und jedesmal hüpft einer der anderen Steine auf seinen richtigen Platz.
1, 10, 2, 3, 4, 5, 6, 7, 8, 9
1, 2, 10, 3, 4, 5, 6, 7, 8, 9
... ... ...
1, 2, 3, 4, 5, 6, 7, 8, 10, 9
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Das waren neun Tauschaktionen bei diesen 10 Steinen.
Die Kette kann man sich auch als Ring vorstellen (und man kann den Ring an jeder beliebigen Stelle öffnen und wieder als Kette legen).

Neu war für Max und Lena bei dieser Aufgabe die gedankliche Multiplikation, aber auch das haben sie gemeistert.

Mehr ->

Alle Steine mit hinten Null liefern bei Multiplikation mit 3 wieder hinten Null - sie bleiben unter sich. 00 bleibt sogar 00 und 50 bleibt 50, weil die Hunderterstelle abgeschnitten wird.
Bilden die restlichen 8 Steine eine Kette oder sind sie paarweise vertauscht? - das war schnell geklärt:
10 --> 30 --> 90 --> 70 --> (10)
20 --> 60 --> 80 --> 40 --> (20)
Also 2 Ketten (Ringe) mit je 4 Steinen macht 2 * 3 = 6 Tauschaktionen

Alle Steine mit hinten Fünf bleiben auch unter sich, weil 5*3 hinten wieder 5 wird.
05 --> 15 --> 45 --> 35 --> (05)
25 --> 75 --> (25)
55 --> 65 --> 95 --> 85 --> (55)
Nochmal 2 Ketten mit je 4 Steinen, wie oben = 6 Tauschaktionen und eine Kette mit 2 Steinen = 1 Tauschaktion

Was ist mit den restlichen 80 Steinen, könnten sie eine Kette bilden?
Nein!! - weiß Max - Weil ungerade mal 3 ungerade ist und gerade mal 3 wieder gerade ist.
Können vielleicht 2 Ketten zu je 40 Steinen gebildet werden? Das haben Max und Lena "ausführlich" untersucht:

01 --> 03 --> 09 --> 27 --> 81 --> 43 --> 29 --> 87 --> 61 --> 83 --> 49 --> 47 --> 41 --> 23 --> 69 --> 07 --> 21 --> 63 --> 89 --> 67 --> (01)
11 --> 33 --> 99 --> 97 --> 91 --> 73 --> 19 --> 57 --> 71 --> 13 --> 39 --> 17 --> 51 --> 53 --> 59 --> 77 --> 31 --> 93 --> 79 --> 37 --> (11)

(Max hat im Kopf gerechnet, Lena hat mit Taschenrechner kontrolliert und die Zahlen auf dem Zettel weggestrichen. Vorsorglich hatten sie alle Zahlen auf einem Zettel notiert, sollte ja keine vergessen werden.
Bei den geraden Spielsteinen musste Lena im Kopf multiplizieren und Max hat kontrolliert.)

02 --> 06 --> 18 --> 54 --> 62 --> 86 --> 58 --> 74 --> 22 --> 66 --> 98 --> 94 --> 82 --> 46 --> 38 --> 14 --> 42 --> 26 --> 78 --> 34 --> (02)
04 --> 12 --> 36 --> 08 --> 24 --> 72 --> 16 --> 48 --> 44 --> 32 --> 96 --> 88 --> 64 --> 92 --> 76 --> 28 --> 84 --> 52 --> 56 --> 68 --> (04)

Max und Lena haben 4 Ketten zu je 20 Steinen erhalten und wissen, mit 4 * 19 = 76 Tauschaktionen können sie die Steine auf die richtigen Plätze befördern.
Alles zusammengezählt ergibt 6 + 6 + 1 + 76 = 89

Hallo Otmar!

Mehr ->

Diesen Lösungsweg habe ich für alle Mäxchens, Lenas und wie sie auch heißen mögen, aufgeschrieben. Mit Deiner sehr interessanten Aufgabe hat sich leider niemand weiter beschäftigt und ich weiß nicht, ob sie es nach dem Lesen Deines Lösungsweges tun werden.
Mit meiner Darstellung wollte ich zeigen, dass auch Kinder (ohne dass sie wissen, was Permutationen, Zyklen, modulo, ... sind) durchaus diese Aufgabe verstehen und lösen können. Kleine Hilfestellungen und vor allem Erklärungen mit einfachen Worten sind da sehr hilfreich.
Es ist ein Spagat, erklärt man es hier mathematisch-wissenschaftlich korrekt und erreicht damit nur eine Minderheit oder versucht man es anders.
Ich weiß, dass dies hier nicht unbedingt ein Forum für Kinder ist. Und deshalb bin ich auch etwas im Zwiespalt. Aber für diese schöne Aufgabe war es mir wert, einen verständlicheren Weg aufzuzeigen, der ohne all diese "Fremdwörter" auskommt.

Gruß Neuling

[Otmar]

Mit Deiner sehr interessanten Aufgabe hat sich leider niemand weiter beschäftigt

Das kann man nicht so sagen. Es hat halt niemand außer dir was gepostet. Aber danke, dass du die Aufgabe interessant findest.

und ich weiß nicht, ob sie es nach dem Lesen Deines Lösungsweges tun werden.

Wenn ich hier nichts zwischen den Zeilen interpretiere, verbleibt eine wahre Aussage, du weißt es nicht. Ich weiss es auch nicht, aber bin guter Hoffnung.

Ich finde es sehr schön, dass du deine Lösung ausführlich niedergeschrieben hast. Ungeachtet Deiner wenig positiven Einstellung gegenüber meiner Lösung, bin ich froh, nun beide Lösungen vergleichen zu können und damit einige deiner Argumente gegen mathematische Werkzeuge, in ein neues Licht zu stellen.

Natürlich stimme ich deinem Vorgehen bei der Lösung zu, denn ich hatte die Problemstellung genau aus dem von dir angeführten Grund (dass sie ohne tiefgehende mathematische Vorkenntnisse lösbar ist) zusammengestellt und mit geeigneten Parametern versehen. Das Spielfeld ist nicht zur Verwirrung der Leser in der Aufgabenstellung erwähnt, sondern

Mehr ->

um dort bereits getauschte Felder auf einfache Weise wegstreichen zu können. Es ist nicht 8x8 oder NxN Felder groß sondern 10x10 Felder groß, um anstelle einer allgemeinen Restklasse zur Zahl N² einfach mit den letzten beiden Stellen auf dem Taschenrechner die Zyklen durchrechnen zu können. Bei mir tippe ich z.B. 1 * 3 = = = ... = und nehme die letzten beiden Stellen zum Durchstreichen der Felder dieses Zyklus. Den Begriff Zyklus verwende ich, da andere Begriffe, z.B. der Begriff Ring, in diesem Bereich der Mathematik schon für etwas anderes vergeben ist http://m.schuelerlexikon.de/ma_abi2011/Ringe.htm und so Verwirrung entstehen könnte.
(Z.B untersucht man hier gerade einen endlichen Ring, den Restklassenring Z/100Z.)
Der Unterschied zwischen unseren beiden Lösungen ist nun der, dass deine Lösung zwar sehr einfach zu verstehen ist, aber dafür müssen alle Zyklen durchgerechnet werden und man muss sich diese Zyklen auch merken. Meine Lösung hatte zum Ziel, die Anzahl der Berechnungen und des nötigen „Speichers“ zu reduzieren mit dem Preis, dass man einige Überlegungen mehr benötigt, als bei der einfachen Lösung. Aber weil gerade in der Praxis effiziente Verfahren zur Lösung mathematischer Probleme sehr wichtig sind (heutzutage ist kein Handy und fast kein Computerprogramm mehr zu finden, dass auf solche optimierten Verfahren verzichten könnte) hatte ich meine Lösung vorgestellt. Der Vergleich beider Lösungen macht vielleicht gerade dieses Problem für „Mäxchen und Lena“ lehrreich und ist vielleicht sogar ein Anreiz, sich mit mathematischen Fremdwörtern und so künstlich erscheinenden Objekten, wie Restklassen zu beschäftigen.
Nebenbei, sowohl Permutationen als auch Restklassen (modulo Rechnungen) sind heutzutage Schulstoff und häufig Bestandteil in der Mathe-Abi Prüfung.
http://m.schuelerlexikon.de/ma_abi2011/Permutationen.htm
http://m.schuelerlexikon.de/ma_abi2011/Restklassen.htm

Vielleich kommt dir meine Lösung aber nur deshalb so unverständlich vor, weil sie noch einige kleinere Überlegungen dem Leser überlässt:
z.B.:

Wegen a(k) = 3^k a(0) kann nun kein anderer Zyklus mehr als 20 Elemente haben und die Zahl der Elemente muss ein Teiler von 20 sein.

Hier muss der Leser zwei kleine indirekte Beweise führen:
1) Angenommen der Zyklus hat m > 20 Elemente, dann bin ich von a(0) nach 20 Schritten noch nicht wieder auf a(0) angekommen. Das steht im Widerspruch zu a(20) = 3^20*a(0) = 1*a(0) = a(0) (modulo 100).
2) Angenommen der Zyklus hat m < 20 Elemente und m ist kein Teiler von 20. Wenn ich dann von a(0) im Zyklus 20 Schritte gehe, dann stehe ich nicht auf a(0), denn würde ich auf a(0) stehen, dann hätte ich den Zyklus eine gewisse (ganzzahlige) Anzahl durchlaufen und m wäre ein Teiler von 20. Da ich nicht auf a(0) stehe muss 3^20*a(0) ungleich a(0) sein, was nicht sein kann, weil 3^20 modulo 100 identisch mit der Zahl 1 ist.

Oder:

Ab 81 können wir jeweils 4 Elemente weiterspringen, da in den übersprungenen Elementen die letzte Ziffer nicht 1 sein kann.

Hier muss der Leser feststellen, dass die übersprungen Zahlen die letzten beiden Ziffern von 81^k * 3 oder 81^k * 9 oder 81^k * 27 sind also auf 3 oder 9 oder 7 enden.

Falls jemand etwas in meinen Lösungen nicht versteht, bin ich gern bereit, ausführlicher zu werden und die in der Mathematik übliche Floskel: „wie man leicht sieht“ mit einer Erklärung versehen.