Spielsteinetausch

[Neuling]

Mäxchen hat ein Spielbrett der Größe 3 x 3 Felder.
Auf jedem Feld liegt ein Spielstein mit der Ziffer 1.
Er hat außerdem noch 8 Spielsteine mit den Ziffern 2 bis 9.

Spielsteinetausch.gif (6.37 KiB) 822-mal betrachtet

Jetzt möchte Mäxchen ein paar Spielsteine auf dem Brett austauschen und zwar so, dass die Summe der Spielsteine in jeder Zeile, Spalte und (3er)Diagonale eine andere ist - also acht verschiedene Summen entstehen. Außerdem soll die Summe aller Steine, die dann auf dem Spielbrett liegen, so klein wie möglich sein.
Wer kann ihm helfen?

[Friedel]

Hallo,
ich habe keinen Weg gefunden, das Rätsel ohne sehr viel Aufwand zu lösen. Ich habe habe eine unsaubere Methode genutzt, um etwas zu finden, von dem ich vermute, dass es eine Lösung ist.

Mehr ->

Ich habe das ganze mit einem einfachen Script mit Brute Force "gelöst". Dabei habe ich einige Kombinationen ausgeschlossen und vermutet, dass es bei der Kombination mit der kleinsten Gesamtsumme eine Reihe (oder Spalte) mit 3 Einser-Steinen gibt. Die dann möglichen Kombinationen habe ich einfach durchprobiert. Dabei bin ich auf 22706 mögliche Kombinationen gekommen, deren kleinste Gesamtsumme 19 ist. Wenn die untere Reihe die Reihe mit den 3 Einsen ist, gibt es 10 Anordnungen mit Gesamtsumme 19.

Mehr ->

513  Lösung 173
421 → 19
111

542  Lösung 644
131 → 19
111

245  Lösung 681
131 → 19
111

145  Lösung 763
231 → 19
111

412  Lösung 899
531 → 19
111

153  Lösung 1427
241 → 19
111

541  Lösung 5187
132 → 19
111

351  Lösung 5410
142 → 19
111

315  Lösung 9152
124 → 19
111

214  Lösung 11515
135 → 19
111

Mehr ->

Da ich jetzt weiß, dass es Kombinationen mit Gesamtsumme 19 gibt, könnte ich das Script leicht optimieren, um ganz sicher zu gehen, dass es keine Anordnung mit Gesamtsumme unter 19 gibt. Aber ich warte lieber ab, ob das vielleicht jemand eleganter lösen kann.

[Friedel]

Ok, das Einkaufen ist schnell gegangen.

Mehr ->

Mit 5 Einsen und je einer 2, 3, 4 und 5 kommt man auf die Gesamtsumme 19. Dass man mit 6 Einsen nicht auf lauter verschieden Summen kommt, kann man relativ leicht überprüfen. Es gibt ja eine überschaubare Zahl von Anordnungen für die 3 Nicht-Einsen. Und immer ist mindestens 1 Nicht-Eins in mindestens 2 Reihen, Spalten oder Diagonalen, die sonst nur Einsen hat.

Es gibt 72 Kombinationen von 5 Einsen und je einer 2, 3, 4 und 5, die alle Bedingungen erfüllen. Wie man die allerdings ohne Programmierung finden kann, weiß ich nicht. Da ja nicht vorher wusste, dass es überhaupt Lösungen mit Summe 19 gibt, musste ich zunächst auch mit größeren Steinen probieren und habe ohne Script nur Lösungen mit Summe 20 und mehr gefunden.

Ich bin gespannt, ob jemand eine Lösung ohne Rechnerunterstützung anbieten kann.

[Neuling]

@Friedel - ja, Mäxchen hat seine Lösungen ganz ohne Rechnerhilfe gefunden.
Ich beschreibe hier mal seine Überlegungen und seinen Weg der Lösungsfindung.
Einiges deckt sich mit deinen Erläuterungen.
Und dass es keine kleinere Gesamtsumme geben kann, folgt aus seinem und auch aus deinem Ansatz.

Mehr ->

1. Überlegung
Kann man durch den Tausch von nur drei Steinen, acht verschiedene Summen erhalten?
Dazu hat Mäxchen einfach mal 3 Steine durch 7, 8, 9 ersetzt.
Egal wie er diese drei Steine platzierte, er hat immer auch identische Reihensummen bekommen.
Fazit: Man muss mindestens 4 oder mehr Steine austauschen.

Falls es mit 4 Austauschsteinen gehen sollte und die Summe ja möglichst klein sein soll, probiert Mäxchen es dann gleich mit 2, 3, 4, und 5.
Auf dem Brett liegen dann 1, 1, 1, 1, 1, 2, 3, 4 und 5 - also Summe 19. Kleiner geht dann nicht!
Damit kann er Reihensummen von 3 (1,1,1), 4 (1,1,2), ... bis 12 (3,4,5) bilden. Einige nur auf eine Art, andere auf zwei Arten.

Je drei dieser Reihensummen (3 Zeilen bzw. 3 Spalten) müssen die Gesamtsumme 19 ergeben:
(3, 4, 12), (3, 5, 11), (3, 6, 10), (3, 7, 9), (4, 5, 10), (4, 6, 9), (4, 7, 8), (5, 6, 8)

Alle Möglichkeiten (3 Zeilensummen und 3 Spaltensummen), die dann evtl. zu einer Lösung führen könnten, sind:
1. (3, 4, 12) und (5, 6, 8)
2. (3, 5, 11) und (4, 6, 9)
3. (3, 5, 11) und (4, 7, 8)
4. (3, 6, 10) und (4, 7, 8)
5. (3, 7, 9) und (4, 5, 10)
6. (3, 7, 9) und (5, 6, 8)

Aus den Möglichkeiten 3, 4 und 5 hat Mäxchen durch "einfaches legen" diese 4 Lösungen gefunden. Durch Drehungen und/oder Spiegelungen kann man daraus weitere Lösungen erstellen.

Spielsteinetausch Lösungen.gif (13.81 KiB) 798-mal betrachtet

@Friedel
Mäxchen hatte nicht den Anspruch - falls es mehrere optimale Lösungen geben sollte - diese alle zu finden!

Mehr ->

Bei deinen 10 Lösungen sind einige Spiegelungen dabei.
Eine Lösung habe ich aber bei dir entdeckt, die hat Mäxchen nicht. Deine Lösung 899.

[Friedel]

Mehr ->

Die Lösungen können ja nicht symmetrisch sein. (Bei einer symmetrischen Anordnung gibt es ja zwangsläufig doppelt vorkommende Summen der Reihen.) Die Spiegelung einer Lösung an der senkrechten Mittelachse erzeugt also eine weitere Lösung. Un die Spiegelung der ursprünglichen Lösung an der waagerechten Mittelachse erzeugt eine 3. Lösung. Und die Spiegelungen an den beiden Diagonalen erzeugen die 4. und 5. Lösung. Außerdem kann man die Lösung um 90°, um 180° und um 270° drehen und kommt so auf Lösung 6 bis 8. Da es insgesamt 72 Lösungen gibt, sollten das also 9 Lösungen sein, die nicht durch (einfaches) Drehen oder Spiegeln aus einer der anderen Lösungen hervorgehen. Mäxchen hat also weniger als die Hälfte der Lösungen gefunden. Aber es ist schon erstaunlich, dass man so einfach mit den richtigen Überlegungen überhaupt zu Lösungen kommt.

Die Aufgabe und auch die Musterlösung hat mit sehr gut gefallen.

[Neuling]

@ Friedel, ich stimme dir im Prinzip zu.

Mehr ->

In einer Grafik habe ich Spiegelungen und Drehungen nochmal verdeutlicht.
Links oben ist die Ausgangslösung. Die "Spiegelachsen" habe ich in rot gekennzeichnet und die Drehungen in blau.

Spiegelungen und Drehungen.gif (8.75 KiB) 785-mal betrachtet

Du schreibst, dass es 72/8 = 9 Lösungen geben soll.
Genannt hast du aber nur 5 Lösungen mit je einer Spiegelung.

Lösung 681 ist Spiegelung zu 644 - Lösung hat Mäxchen auch
Lösung 5187 ist Spiegelung zu 763 - Lösung hat Mäxchen auch
Lösung 5410 ist Spiegelung zu 1427 - Lösung hat Mäxchen auch
Lösung 9152 ist Spiegelung zu 173 - Lösung hat Mäxchen auch
Lösung 11515 ist Spiegelung zu 899 - diese Lösung hat Mäxchen nicht.

Gibt es noch weitere Lösungen? Wenn ja, kannst du sie noch nennen?

Habe soeben noch Lösungen gefunden:

Mehr ->

1 3 5
1 1 1
2 1 4

3 1 1
1 1 1
4 2 5

[Neuling]

Und nochmal gesucht und zwei weitere Lösungen gefunden:

Mehr ->

113     115
111     111
425     432

Wenn Friedel mit der Anzahl der Lösungen recht hat, haben wir jetzt alle Lösungen gefunden.

Mehr ->

111     111     111     111     111     135     311     113     115
131     132     124     142     135     111     111     111     111
245     541     315     351     214     214     425     425     432

[Friedel]

Mein Script hat folgendes ausgespuckt:

Mehr ->

513  Lösung 1
421 → 19
111
542  Lösung 2
131 → 19
111
245  Lösung 3
131 → 19
111
145  Lösung 4
231 → 19
111
412  Lösung 5
531 → 19
111
153  Lösung 6
241 → 19
111
541  Lösung 7
132 → 19
111
351  Lösung 8
142 → 19
111
315  Lösung 9
124 → 19
111
214  Lösung 10
135 → 19
111
415  Lösung 11
311 → 19
211
451  Lösung 12
131 → 19
211
511  Lösung 13
431 → 19
211
415  Lösung 14
113 → 19
211
524  Lösung 15
111 → 19
311
425  Lösung 16
111 → 19
311
541  Lösung 17
121 → 19
311
121  Lösung 18
541 → 19
311
513  Lösung 19
211 → 19
411
215  Lösung 20
311 → 19
411
215  Lösung 21
113 → 19
411
432  Lösung 22
111 → 19
511
234  Lösung 23
111 → 19
511
413  Lösung 24
211 → 19
511
211  Lösung 25
431 → 19
511
121  Lösung 26
431 → 19
511
511  Lösung 27
431 → 19
121
311  Lösung 28
541 → 19
121
115  Lösung 29
134 → 19
121
113  Lösung 30
145 → 19
121
412  Lösung 31
111 → 19
531
214  Lösung 32
111 → 19
531
311  Lösung 33
121 → 19
541
111  Lösung 34
132 → 19
541
111  Lösung 35
142 → 19
351
211  Lösung 36
131 → 19
451
514  Lösung 37
311 → 19
112
154  Lösung 38
131 → 19
112
514  Lösung 39
113 → 19
112
115  Lösung 40
134 → 19
112
531  Lösung 41
111 → 19
412
135  Lösung 42
111 → 19
412
111  Lösung 43
531 → 19
412
114  Lösung 44
311 → 19
512
114  Lösung 45
113 → 19
512
511  Lösung 46
111 → 19
432
115  Lösung 47
111 → 19
432
111  Lösung 48
131 → 19
542
524  Lösung 49
111 → 19
113
425  Lösung 50
111 → 19
113
145  Lösung 51
121 → 19
113
121  Lösung 52
145 → 19
113
511  Lösung 53
211 → 19
413
411  Lösung 54
211 → 19
513
111  Lösung 55
421 → 19
513
111  Lösung 56
241 → 19
153
512  Lösung 57
311 → 19
114
315  Lösung 58
112 → 19
114
512  Lösung 59
113 → 19
114
531  Lösung 60
111 → 19
214
135  Lösung 61
111 → 19
214
111  Lösung 62
135 → 19
214
115  Lösung 63
112 → 19
314
112  Lösung 64
311 → 19
514
112  Lösung 65
113 → 19
514
311  Lösung 66
111 → 19
524
113  Lösung 67
111 → 19
524
511  Lösung 68
111 → 19
234
115  Lösung 69
111 → 19
234
112  Lösung 70
131 → 19
154
432  Lösung 71
111 → 19
115
234  Lösung 72
111 → 19
115

Jeweils 3 Zeilen sind eine Lösung. Links stehen die 9 Werte der Spielsteine, rechts neben der ersten Zeile die Nummer die Lösung, darunter nach einem Pfeil die Gesamtsumme.

Das Script probiert alle Kombinationen der Z9ffern 1 bis 5 durch und prüft bei jeder Kombination ob Ziffern >1 mehrfach verwendet wurden und ob die Summen der Spalten Reihe und diagonalen mehrfach vorkommen.

[Neuling]

@ Friedel - habe unter allen deinen Lösungen zwei weitere Lösungen entdeckt ...

Mehr ->

und diese jetzt in meiner "Sammlung" ergänzt.
Damit haben wir insgesamt 11 Lösungen:

111     111     111     111     111     135     311     113     115     115     135
131     132     124     142     135     111     111     111     111     111     111
245     541     315     351     214     214     425     425     432     234     412

[Friedel]

Ich musste eine wenige überlegen, warum sowas möglich ist.

Mehr ->

Wir hatten ja festgestellt, dass es zu jeder Lösung 8 verschiedene Permutationen gibt, die auch Lösungen sind. Dabei unterscheiden sich aber nur die jeweilige Lösung und ihre 8 Permutationen voneinander. Es kann durchaus passieren, dass die Permutationen verschiedener Lösungen gleich sind. Dass 11 Lösungen mit ihren Permutationen insgesamt trotzdem nur 72 Anordnungen sind, ist also kein Widerspruch.