Antworte auf:  Rätsel mit Münzen verschieben aus "Thinking Mathematically" von Robinsson
Forum:  Kombinatorik & Graphentheorie, moderiert von: matroid

[Zur Forum-Gliederung] [Wie man Fragen beantwortet] [Themenstart einblenden]

  Alle registrierten Mitglieder können Mitteilungen schreiben.
Benutzername:
Passwort:
Nachricht-Icon:                   
                  
              
Nachricht:


 
 


Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
 Show Preview      Write using fedgeo formula editor or Latex.

Smilies for your message:
😃 😄 😁 🙂 🙃 😉 🤗 🤫 🤔 🙄 😴 🤒 😎 😮 😲 😂
🙁 😖 😒 😐 😡 👌 👍 👎 🤢 🤧 🥵 🥶 😵 🤯 😛 😷
Optionen: Deaktiviere HTML in dieser Nachricht
Deaktiviere MATHML in dieser Nachricht. Wenn Dein Text $-Zeichen enthält, die nicht LaTeX-Formeln begrenzen.
Deaktiviere Smilies in dieser Nachricht
Zeige die Signatur (Kann in 'Mein Profil' editiert werden.)
    [Abbrechen]
 
Beachte bitte die [Forumregeln]


Themenübersicht
haribo
Senior
Dabei seit: 25.10.2012
Mitteilungen: 2575
Herkunft:
 Beitrag No.48, eingetragen 2020-08-12 20:40    [Diesen Beitrag zitieren]

n=5 in 7 Zügen gabs  schon in #32 und #34

Hast du ne Idee für ne Argumentation wie es um n=6 bestellt ist


viertel
Senior
Dabei seit: 04.03.2003
Mitteilungen: 27482
Herkunft: Hessen
 Beitrag No.47, eingetragen 2020-08-12 20:19    [Diesen Beitrag zitieren]
\(\begingroup\)\(\newcommand\d{\mathop{}\!\mathrm{d}}\)
Dann hätte ich noch $n=5$ zu bieten:


Es scheint sich ein Schema abzuzeichnen, aber ich habe es noch nicht herausdestillieren können🤔
\(\endgroup\)

haribo
Senior
Dabei seit: 25.10.2012
Mitteilungen: 2575
Herkunft:
 Beitrag No.46, eingetragen 2020-08-12 18:20    [Diesen Beitrag zitieren]

prima viertel,
wenn man einen zug vorher aufhört lässt sich n auch beliebig um je 4 erweitern, die beiden farbflächen sind zug-gleich

in einem letzten zug kann man dann ggfls immer noch GGGGkkkkGGGGkkkk....herstellen

damit kommt man für n= 0 mod4 anzahlen immer mit maximal 2n+1−4 zügen aus
(das +1, hier den 9.zug kann man bestimmt noch wegbekommen)
haribo


viertel
Senior
Dabei seit: 04.03.2003
Mitteilungen: 27482
Herkunft: Hessen
 Beitrag No.45, eingetragen 2020-08-12 16:31    [Diesen Beitrag zitieren]
\(\begingroup\)\(\newcommand\d{\mathop{}\!\mathrm{d}}\)
Meine Lösung für $n=4$ in 5 Zügen (das Beste, was ich hier im Thread gefunden habe, waren 6 Züge), wobei beim letzten Zug noch entschieden werden kann, ob die kleinen Kreise nach links oder nach rechts kommen:
\(\endgroup\)

Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6571
Herkunft: Niedersachsen
 Beitrag No.44, eingetragen 2020-08-12 14:44    [Diesen Beitrag zitieren]

2020-08-12 13:47 - haribo in Beitrag No. 43 schreibt:
... damit kommt man für n= 0 mod4 anzahlen immer mit maximal $2,5n-4$ zügen aus

und nun bin ich etwas durcheinander ob das eine verbesserung gegenüber deiner zugzahl laut frage 2) darstellt oder sie nur bestätigt???
Ich war mir relativ sicher, dass man Verbesserungen zu meinem angegebenen Verfahren erzielen kann, z.B. indem man den/die letzten Achterblock/-blöcke zusammen mit dem "Rest" sortiert.
Die Frage ist, ob sich dadurch nur eine konstanten Anzahl (O(1) in Landau-Schreibweise) an Zügen einsparen lässt, oder ob man den Faktor vor dem n (derzeit also 2.5) verkleinern kann.

Sieht jemand eine Chance den Fall mit 6 großen und 6 kleinen Münzen durchzurechnen?


haribo
Senior
Dabei seit: 25.10.2012
Mitteilungen: 2575
Herkunft:
 Beitrag No.43, eingetragen 2020-08-12 13:47    [Diesen Beitrag zitieren]

2020-08-10 14:42 - Kitaktus in Beitrag No. 41 schreibt:

Offene Fragen:
1) Gibt es eine Lösung für $n=6$?
2) Kommt man im Allgemeinen mit weniger als $2.5n + O(1)$ Zügen aus?

ich habe hier bei gleichem $4G+4k$ block-ansatz eine lösung die für $n=4$ ohne rechtsverschiebung auskommt, weil ich bei zwei zügen blöcke nach ganz aussen auslagere, die beiden aussenliegenden blöcke werden in dieser zugfolge gar nicht bewegt,(das pinke kreuz soll das symbolisieren,
eben weil die äusseren nicht bewegt werden kann mit gleicher zugzahl auch ein umsortierung für $n=3$ durchgeführt werden

im unterschied zu deiner lösung braucht sie 7 züge, dieser anfängliche nachteil gleicht sich aber dann im 2. block also für $n=8$  mit dann auch nur $2X6$ zügen bis zu einer sortiereng $4G4k4G4k$ wieder aus


füge ich einen zweiten (oder beliebig weitere) 8er blöcke links daneben
dann spare ich züge, weil das auslagern nur einmal erfolgen muss bzw eben erst für den letzten block das zurücklagern erfolgt, die blöcke werden dabei nicht wirklich nacheinander sortiert, sondern es werden züge vom 2. block vorgezogen, eben um weitere auslager bewegungen direkt dorthin ausführen zu können

nach jetzt $2x6=12$ zügen ist der zweite block auch lagegetreu in $GGGGkkkk$ sortiert, (mit jeweils $6$ weiteren zügen könnte der 3. oder beliebig weitere $n=4er$ blöcke ebenso durchsortiert werden)

dann ab zug 12 (unter der pinken querlinie)kann jeder dazugekommene block mit 4 weiteren zügen an den linkesten existierenden $GGGGkkkk$ drangehängt werden

also mit $2x6+4=16$zügen ist $n=8$ erledigt
jeder weiter dazukommende 4er block bedeutet also wohl $6+4=10$ weitere züge damit kommt man für n= 0 mod4 anzahlen immer mit maximal $2,5n-4$ zügen aus

und nun bin ich etwas durcheinander ob das eine verbesserung gegenüber deiner zugzahl laut frage 2) darstellt oder sie nur bestätigt???

zu frage 1) hab ich auch bisher keine antwort

@robinsson, hier haben wir jetzt ein system konstruiert welches irgendwo immer den zwischenschritt hat aneinandergereite $GGGGkkkk$ sequenzen zu haben(z.B. zeile 12 im unteren bild), welche sich dann pro block mit 4 zügen eindeutig und einfach weiter verlegen lassen, ich könnte mir vorstellen dass es auch konstruktionen gibt welche als zwischenschrit eben $GGkkGGkk$ sequenzen haben (wichtig ist ja zum weiterlegen nur das die einzelteile der sequenz jeweils aus einer geraden anzahl münzen bestehen), und dass zwischenbild könnte dann analog zu dem anscheinend erforderlichen zwischenschritt BWBWBW... bei den fröschen gesehen werden ???

haribo


Robinsson
Aktiv
Dabei seit: 15.07.2020
Mitteilungen: 21
Herkunft:
 Beitrag No.42, eingetragen 2020-08-11 19:22    [Diesen Beitrag zitieren]

Hi,

hab dein Ansatz nachvollziehen können. Die Sache wieso ich mit dieser Aufgabe noch etwas hadere, ist, dass ich nach wie vor den Zusammenhang mit der Aufgabe "Laubfrösche" auf S. 59 in Kap. 3 aus dem selben Buch
"Mathematisch denken" nicht mal ansatzweise durchblickt
habe. Wie AlphaSigma im Beitrag No 9 geschrieben hat, wurde
für diese Aufgabe der Hinweis gegeben an die Laubfrösche-Aufgabe
zu denken.  

Ich kann mal die Aufgabenstellung der gemeinten Aufgabe erläutern:

Laubfrösche



Zehn Stöpsel in zwei unterschiedlichen Farben stecken wie unten
gezeichnet in einem Brett mit Löchern. Ziel ist es, die
schwarzen und weißen Stöpsel gerade zu vertauschen.
Dabei dürfen aber die schwarzen Stöpsel nur nach rechts
und die weißen Stöpsel nur nach links bewegt werden.
Es ist aber zulässig, über einen anderen Stöpsel hinweg
in das einzige jeweils vorhandene Loch zu springen.
Ist dies durchführbar?




In der Ausarbeitung kommt man zur folgenden Erkenntnis,
die zur allgemeingültigen Strategie führt:



Danach richtet sich da auch die allgemeine Strategie. Die Farben müssten immer alterieren.

Jetzt frage ich mich, ob bei dieser Aufgabe zu
"Münzenverschiebung" auch so gedacht war, dass sich
eine allgemeingültige Strategie herauskritallisieren sollte,
nach der mein allgemeines Vorgehen im n-n-Fall richtet. Nun haben wir
3-3, 4-4 und 5-5 durchgespielt und irgendwie scheint
keine ähnliche Strategie auffindbar zu sein
wie es bei Laubfröschen der
Fall war.

Bei Laubfröschen ist es ja eine gewisserweise Strategie über eine "Invariante". Jeder Zug ist im Grunde richtig, solange danach die Farben alternierend angeordnet sind, sonst falsch. Diese Sache mit alternierenden Farben ist wie eine Art verallgemeinerte Invariante, die bei jedem Zug nicht zerstört werden darf.

Deine Lösung ist nach Teile-und-Herrsche-Strategie aufgebaut. Sie ist korrekt, aber irgendwie schein dieser Tipp mit Laubfröschen in der Luft zu hängen. Oder siehst du vielleicht wie Tipp mit den Laubfröschen gemeint war?


Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6571
Herkunft: Niedersachsen
 Beitrag No.41, eingetragen 2020-08-10 14:42    [Diesen Beitrag zitieren]

Hier mein Ansatz zur Lösung (einschließlich einer oberen Schranke für die Zugzahl) aller Ketten mit $n$ großen und $n$ kleinen Münzen für $n\not\equiv2$ (mod 4).

Wir gehen davon aus, dass die Kette links mit einer großen Münze beginnt. Im weiteren Verlauf bezeichne ich große Lücken mit "-" und kleine mit "."
Wir unterteilen nun die ganze Kette von rechts in Achterblöcke mit je vier großen (G) und vier kleinen Münzen (K). Links bleiben dann 0, 2 oder 6 Münzen übrig.

n = 0 (mod 4)
..-.-.-.-.|GKGKGKGK|...|GKGKGKGK|
 
-------------------------------------
n = 1 (mod 4)
..-.-.-.GK|GKGKGKGK|...|GKGKGKGK|
-------------------------------------
 
n = 3 (mod 4)
..-.GKGKGK|GKGKGKGK|...|GKGKGKGK|

Im Fall n = 3 (mod 4) sortieren wir links schon mal vor:
n = 0 (mod 4)
..-.GKGKGK|GKGKGKGK|...|GKGKGKGK|
..KGG.-KGK|GKGKGKGK|...|GKGKGKGK|
..KGGGKK-.|GKGKGKGK|...|GKGKGKGK|
KKKGGG..-.|GKGKGKGK|...|GKGKGKGK|

Im nächsten Schritt sortieren wir von rechts die Blöcke um
|GKGKGKGK-...
|GKGKG.-KKG..
|GKGKG.-..GKK
|GKG.-..KGGKK
|-.GGK..KGGKK
|-.GGKKKKGG..
|-.--KKKKGGGG (Die Platzierung der letzten beiden G benötigt mehr Platz.)
Der Block ist somit in 6 Zügen sortiert und dabei um drei große und eine kleine Lücke nach rechts gerutscht. Mehr Platz wird rechts auch nicht zum Umsortieren benötigt.
Für die Sortierung der weiter links stehenden Blöcke wurde durch die Verschiebung nach rechts also der nötige Platz geschaffen.

Nachdem die Achterblöcke sortiert sind und das linke Ende ggf. ebenfalls sortiert wurde, kann man die Gesamtlösung zusammensetzen.
Im Fall n = 0 (mod 4) beginnen wir mit dem linken Achterblock KKKKGGGG.
Im Fall n = 1 (mod 4) mit dem kleinen Ende GK.
Im Fall n = 3 (mod 4) mit dem sortierten Ende KKKGGG.
Alle folgenden sortierten Achterblöcke arbeiten wir von links nach rechts folgendermaßen ab:
Im Fall n=0 und n=3 (mod 4) hängen wir KK ganz links an, während GG soweit nach links verschoben wird, dass es bündig liegt. Im Fall n=1 (mod 4) ist es genau umgekehrt.
Für jeden Achterblock brauchen wir also vier weitere Züge. Am Ende sind alle Münzen sortiert.

Zur Zugzahl:
Sei $n=4m+k$ mit $k\in\{0,1,3\}$.
1. Fall $k=0$
Es werden $6m$ Züge zur Vorsortierung der Achterblöcke benötig, sowie $4\cdot(m-1)$ Züge zum Verschieben der Achterblöcke (außer dem ersten).
Zusammen sind das $10m-4$ Züge.
2. Fall $k=1$
Es werden $6m$ Züge zur Vorsortierung der Achterblöcke benötig, sowie $4\cdot m$ Züge zum Verschieben der Achterblöcke (außer dem ersten).
Zusammen sind das $10m$ Züge.
3. Fall $k=3$
Es werden 3 Züge zur Vorsortierung des linken Endes und $6m$ Züge zur Vorsortierung der Achterblöcke benötig, sowie $4\cdot m$ Züge zum Verschieben der Achterblöcke (außer dem ersten).
Zusammen sind das $10m+3$ Züge.

Ist $n$ mindestens 5, so können wir einen Zug einsparen. Der letzte Zug bei der Sortierung des letzten Achterblockes ist unnötig.

Nachdem wir uns relativ sicher sind, dass es für $n=2$ keine Lösung gibt, wäre der nächste offene Falle $n=6$.
Gibt es hier eine Lösung, dann -- nach dem selben Induktionsprinzip -- auf für alle größeren $n\equiv2$ (mod 4).

Offene Fragen:
1) Gibt es eine Lösung für $n=6$?
2) Kommt man im Allgemeinen mit weniger als $2.5n + O(1)$ Zügen aus?


Robinsson
Aktiv
Dabei seit: 15.07.2020
Mitteilungen: 21
Herkunft:
 Beitrag No.40, eingetragen 2020-08-08 20:19    [Diesen Beitrag zitieren]

Andere Strategie, die ich mir noch überlegt habe, ob man das ganze gewisserweise "fließbarartig" lösen könnte.
Damit meine ich eine Strategie für einen beliebigen n-n Block so aussehen könnte, dass
wir versuchen rechts immer weiter das Paarmuster $...SSLLSSLL$ auszubauen
und auf der "Baustelle" im Inneren periodisch immer zum wiederkehrenden Muster zu gelangen. Da n endlich, wird das irgendwann enden, aber solange es noch nicht der Fall ist, wiederholen wir die Routine immer wieder. Vielleicht wird es einfacher wenn ich skizziere was ich meine.

Wir starten mit dem rechten Ende $[...] LSLSLSLSLS$ eines n-n-Blocks, von links werden natürlich neue Kreise immer dazukommen für n groß genug und das rechte Ende werden schrittweise zu $[...]SSLLSSLL$-Form umbauen.

<- das ist der Zustand, zu den wir periodisch immer zurückkehren werden

Wir arbeiten pro Zyklus nur mit den ersten acht Buchstaben rechts, andere bleiben in diesem Schritt ungerührt:

Coins
[...]LSLSLSLSLSLS
[...]LSLSLSLSLS-.LS
[...]LSLSL.-SLSSLLS
[...]LSLSLLSSLSSL
[...]LSLS--SSLSSLLL
[...]LSLS--..LSSLLLSS 
[...]LSLS-.-.LSSLLLSS 
 

Wir schauen nun nur ! auf den Abschnitt $LSLS-.-.LSSL$.

Sieht jemand eine Möglichkeit $LSLS-.-.LSSL$ zu einer der folgenden Kombinationen unzuformen in einer nicht allzu umständlichen Weise:

Entweder zu $-.-.LSSLLLSS$ oder $LSSL-.-.LLSS$ oder $LLSSLSSL-.-.$ oder
$SSLLLSSL-.-.$? Jede der oberen Formen ist leicht zu $-.-.LSSLLLSS$ unformbar.
Und danach können wir die Prozedur wiederholen bis wir am Ende angekommen sind.






Robinsson
Aktiv
Dabei seit: 15.07.2020
Mitteilungen: 21
Herkunft:
 Beitrag No.39, eingetragen 2020-08-08 20:18    [Diesen Beitrag zitieren]

Hi Leute,

ich war letzte Woche auf Reise und konnte leider nicht der Diskussion teilnehmen. Ich wollte nochmal zwei verallgemeinerte Strategien diskutieren, die ich aus den Beispielen zu 4-4 und 5-5 erschlossen habe. Wenn jemand etwas einfacheres Muster erkannt hat, ist natürlich eingeladen ihn zu präsentieren.

Also eine Strategie wäre tatsächlich rekursiv vorzugehen:
 
Wir starten mit einen n-n Block $LSLSL... SLS$ und transportieren schrittweise das Innere "[...]" von $L[...]S$ möglichst weit weg von übrig bleibendem $L.-. ... .-S$, wenden Rekursion auf den wegtransportierten $(n-1)-(n-1)$ Block an, bekommen also geordneten $(n-1)-(n-1)$ Block $LLL ... SSS$ und bringen ihn schrittweise zurück ins Innere von $L.-.- ... .-.-S$.




tactac
Senior
Dabei seit: 15.10.2014
Mitteilungen: 1827
Herkunft:
 Beitrag No.38, eingetragen 2020-08-03 21:48    [Diesen Beitrag zitieren]

2020-08-03 21:29 - StrgAltEntf in Beitrag No. 37 schreibt:
Meinst du, dass dadurch sogar noch schnellere Lösungen möglich sind? Vielleicht nicht für n = 5, aber für große n?
Kann schon sein. Aber ich habe die Vermutung, dass solche "Zusatzlücken", wenn sie denn zu einer Lösung führen, durch Umordnen der Züge vermieden werden können.


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6237
Herkunft: Milchstraße
 Beitrag No.37, eingetragen 2020-08-03 21:29    [Diesen Beitrag zitieren]

2020-08-03 19:38 - tactac in Beitrag No. 35 schreibt:
Übrigens ist die Größe der Lücken so unbekannt, dass nicht einmal angenommen wird, dass eine kleine Münze in eine große Lücke passt.
Die Züge werden auch so gesucht, dass so ein Münzenpaar nie weiter nach rechts geschoben wird, als so weit, dass es die zuvor rechteste Münze berührt (nach links analog).

Meinst du, dass dadurch sogar noch schnellere Lösungen möglich sind? Vielleicht nicht für n = 5, aber für große n?


haribo
Senior
Dabei seit: 25.10.2012
Mitteilungen: 2575
Herkunft:
 Beitrag No.36, eingetragen 2020-08-03 20:26    [Diesen Beitrag zitieren]

nach tactacs schönem n=5 hab ich n=7 versucht, es bildet sich langsam ein prinzip heraus
meine lösung ist 12, ich vermute das es mit 11 auch gehen könnte

3-->3
5-->7
7-->11
wäre ja mal ne einfache reihe für die ungeraden n´s



der gedanke mit den zwei primdurchmessern ist allerdings sowas von mist, es wird ja addiert und nicht multipliziert... 18=6x3=3x5+3 ... unglaublich wie falsch ich liege
haribo

nachtrag: dass macht diese lösung unmöglich für verschiedene durchmesser,










tactac
Senior
Dabei seit: 15.10.2014
Mitteilungen: 1827
Herkunft:
 Beitrag No.35, eingetragen 2020-08-03 19:38    [Diesen Beitrag zitieren]
\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner} \newcommand{\upamp}{\mathbin {⅋}}\)
2020-08-03 19:27 - StrgAltEntf in Beitrag No. 34 schreibt:
Hast du das mit einem Programm gefunden? Falls ja, welches ist die kürzeste Lösung für n=4, die dein Programm findet?

Ja. Die Lösung, die für $n=4$ gefunden wird, ist
coins
Large Small Large Small Large Small Large Small
Large Small Large Small Large (1,1) Small Small Large
Large Small Large Small Large (3,1) Large Small Small
Large Small Large (3,1) Small Large Large Small Small
Large Large Small (2,0) Small Large Large Small Small
Large Large Small Small Small Small Large Large
Small Small Small Small Large Large Large Large

Übrigens ist die Größe der Lücken so unbekannt, dass nicht einmal angenommen wird, dass eine kleine Münze in eine große Lücke passt.
Die Züge werden auch so gesucht, dass so ein Münzenpaar nie weiter nach rechts geschoben wird, als so weit, dass es die zuvor rechteste Münze berührt (nach links analog).
\(\endgroup\)

StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6237
Herkunft: Milchstraße
 Beitrag No.34, eingetragen 2020-08-03 19:27    [Diesen Beitrag zitieren]

2020-08-03 17:22 - tactac in Beitrag No. 32 schreibt:
Hier mal eine Lösung für 5 große und kleine Münzen unbekannter Größe.
Löcher werden als Paare (x,y) dargestellt, wobei x die Anzahl der kleinen und y die Anzahl der großen Münzen ist, die hineinpassen. Löcher am Anfang und Ende werden weggelassen.

@tactac:
Super! Hier noch einmal in verkürzter Darstellung. - steht für eine große und . für eine kleine Lücke.
Coins
LSLSLSLSLS
L-.SLSLSLSSL
LLSSLS-.LSSL
LLSS--..LSSLLS
LLSS..LLLSS--S
LLSS..LLL--..SSS
LL....LLL--SSSSS
--....LLLLLSSSSS

Hast du das mit einem Programm gefunden? Falls ja, welches ist die kürzeste Lösung für n=4, die dein Programm findet?

2020-08-03 18:03 - haribo in Beitrag No. 33 schreibt:
1) die konstruktion #29 funktionierte auch schon fehlerfrei
2) mir gings aber um die allgemeine idee

@haribo:
1) ich hatte mich verzählt, sorry
2) das ist dir gelungen


haribo
Senior
Dabei seit: 25.10.2012
Mitteilungen: 2575
Herkunft:
 Beitrag No.33, eingetragen 2020-08-03 18:03    [Diesen Beitrag zitieren]

alles überprüft und neu gezeichnet, jetzt mit zwei primzahl-durchmessern 3+5 da kann es ja wohl hoffentlich gar keine lückenfehler mehr geben können...

-die konstruktion #29 funktionierte auch schon fehlerfrei

-viertels lösung aus #3 war auch für beliebige durchmesser, damit wirds also einige züge besser, also brauch ich in dem system dann 9 züge für n=4


ich meine damit ist jetzt der nachweis über die machbarkeit von allen n>=3 geführt

nachtrag: den zug 1 lege ich hier in zug 5 unverändert weiter... damit könnte ich zug 1 auch ersatzlos streichen,
dito zug 6 kann gestrichen werden er wird in 9 weitergelegt
dann wären es 7 züge, mir gings aber um die allgemeine idee


tactac
Senior
Dabei seit: 15.10.2014
Mitteilungen: 1827
Herkunft:
 Beitrag No.32, eingetragen 2020-08-03 17:22    [Diesen Beitrag zitieren]

Hier mal eine Lösung für 5 große und kleine Münzen unbekannter Größe.
Löcher werden als Paare (x,y) dargestellt, wobei x die Anzahl der kleinen und y die Anzahl der großen Münzen ist, die hineinpassen. Löcher am Anfang und Ende werden weggelassen.
Coins
Large Small Large Small Large Small Large Small Large Small
Large (1,1) Small Large Small Large Small Large Small Small Large 
Large Large Small Small Large Small (1,1) Large Small Small Large 
Large Large Small Small (2,2) Large Small Small Large Large Small 
Large Large Small Small (2,0) Large Large Large Small Small (0,2) Small 
Large Large Small Small (2,0) Large Large Large (2,2) Small Small Small 
Large Large (4,0) Large Large Large (0,2) Small Small Small Small Small 
Large Large Large Large Large Small Small Small Small Small 


haribo
Senior
Dabei seit: 25.10.2012
Mitteilungen: 2575
Herkunft:
 Beitrag No.31, eingetragen 2020-08-03 17:17    [Diesen Beitrag zitieren]

Ich hab doch extra 5 und 1 als Durchmesser gewählt damit nicht son Problem auftreten kann in Zeile 9... grrr muss ich prüfen

War Viertels Lösung mit 3 Zügen nicht beschränkt auf Coins im Verhältnis 1zu2 ?

Das Problem für n=5 besteht nicht hab ich gerade herausgefunden, beim zurücklegen sind es 2x4 coins da kann man problemlos die Reihenfolge umdrehen!


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6237
Herkunft: Milchstraße
 Beitrag No.30, eingetragen 2020-08-03 16:26    [Diesen Beitrag zitieren]

@haribo:

Wenn ich mich nicht verzählt habe, ist die Lücke in Zeile 9 zwischen den drei roten und drei gelben Blöcken nur so breit wie ein gelber Block, sodass da nicht zwei gelbe Blücke reinpassen.

Aber viertel hat ja schon in #3 gezeigt, wie man in drei Zügen von KGKGKG nach GGGKKK gelangt.

Somit hätten wir für das 4-4-Problem eine Lösung mit 9 Zügen.

Wie ich allerdings außerdem sehe, lässst sich diese Methode nicht von 4 nach 5 anwenden.


haribo
Senior
Dabei seit: 25.10.2012
Mitteilungen: 2575
Herkunft:
 Beitrag No.29, eingetragen 2020-08-03 15:53    [Diesen Beitrag zitieren]

#22 hatte ich nur geschrieben weil ich diesbezüglich mit deiner notation hadere, auch mit $\overline{GK}$ als lücke muss man dann sowohl GK als auch  ggfls KG hineinpositionieren... und wenn man dann beispielsweise irgendwann die lücke $\overline{GKGGKKGG}$  hätte, kann man eben auch nicht simpel entscheiden ob $\overline{GGGGGG}$  da hineinpassen würde oder nicht, wäre ja möglich dass es übertritt

also #22 sollte NUR mit gleichgrossen weingläsern gehen aber nicht mit verschiedenen coins




für den schritt die reihe um ein n zu erweitern hätte ich diese idee:
welche eher nicht minimal ist aber immerhin evtl zeigt dass es für verschieden grosse coins n>=3 immer eine lösung gibt

die neuen coins hab ich blau gezeichnet mit ihnen wird n=3 zu n=4 erweitert, sie werden nie bewegt
ich lagere in den n-1 ersten schritten alle mittleren coins aus, bearbeite sie dann rechts ausserhalb
hier in den zeilen 4-10 nach der lösung von n=3
>hab auf die schnelle nicht gefunden ob ihr für beliebige durchmesser bei n=3 eine bessere lösung als 7 schritte hattet...?<
und dann in den zeilen 11-13 lagere ich sie wieder zurück

also n=4 hätte dann eine lösung mit 6 schritten mehr als die beste n=3 lösung, n=5 nochmal 8 mehr usw



Robinsson
Aktiv
Dabei seit: 15.07.2020
Mitteilungen: 21
Herkunft:
 Beitrag No.28, eingetragen 2020-08-03 14:57    [Diesen Beitrag zitieren]

2020-08-03 14:47 - StrgAltEntf in Beitrag No. 27 schreibt:


Dein Vorgehen in #11 mit 7 Schritten sieht aber gut und richtig aus.


Habe aber die Hoffnung noch nicht aufgegeben, das es "schöner" geht. Irgendeine Invariante, die bei jedem erlaubten Zug erhalten bleibt, und sich bei $GKGK$ und $GGKK$ bzw $KKGG$ unterscheidet, wäre natürlich toll. Dann wär die Behauptung dass Fall 2-2 unlösbar ist ein Einzeiler.


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6237
Herkunft: Milchstraße
 Beitrag No.27, eingetragen 2020-08-03 14:47    [Diesen Beitrag zitieren]

2020-08-03 14:39 - Robinsson in Beitrag No. 25 schreibt:
@StrAltEntf:

den Übergang von 5 nach 6 in deiner Modifikation von haribo's Algo verstehe ich nicht.

Den Schritt von 5 nach 6 hatte ich gar nicht modifiziert. Hier bleibt eine Macke.

Dein Vorgehen in #11 mit 7 Schritten sieht aber gut und richtig aus.


Robinsson
Aktiv
Dabei seit: 15.07.2020
Mitteilungen: 21
Herkunft:
 Beitrag No.26, eingetragen 2020-08-03 14:39    [Diesen Beitrag zitieren]

Ich habe mir noch ein Paar Gedanken gemacht und denke
nach wie vor, dass viertels Algorithmus sich retten lässt,
wenn man ab dem drittletzten Schritt in seiner Animation anders argumentiert.
Bis zum 4. Schritt stimmt er mit den Algorithmen von haribo und StrAltEntf überein.
Hier mein Vorschlag für den ganzen Algorithmus:

$GKGKGKGK$

$GKGKG\overline{KG}KKG$

$\overline{GK}GKG\overline{KG}KKGGK $

$\overline{GK}\overline{GK}GGKKKGGK= GGKKKGGK$  die unterscheiden sich ja nur um ein Shift

$GGKKKGGK$

$GGGGKKK\overline{GG}K$

$GGGGK\overline{GG}KKK$   das ist legitim, wir müssen nur Annehmen, dass $KK$ in $GG$ passt

$GGG\overline{GG}GKKKK$  genauso: $GK$  passt in $GG$

$\overline{GG}GGGGKKKK=GGGGKKKK$

Das scheint logisch zu sein, oder sieht jemand einen Denkfehler? Das einzige, was ich als Annahme benutze, ist, dass der Durchmesser von $G$ größer/gleich der von $K$ ist. Wenn nicht, dann können wir "spiegelverkehrt" argumentieren, also dieselben Schritte nur gespiegelt auf der senkrechten Achse durch die Mitte von $GKGKGKGK$.

Wenn die Lösung ok ist, sieht jemand ein Muster oder eine Regelmäßigkeit, das oder die schon bei 3-3 erkennbar war und auf 5-5, 6-6 bzw n-n ausweitbar ist?


Robinsson
Aktiv
Dabei seit: 15.07.2020
Mitteilungen: 21
Herkunft:
 Beitrag No.25, eingetragen 2020-08-03 14:39    [Diesen Beitrag zitieren]

@StrAltEntf:

den Übergang von 5 nach 6 in deiner Modifikation von haribo's Algo verstehe ich nicht.
Wie bringst du $KK$ in die $GG$-Lücke? Ich finde es führt etwas zur Verwirrung,
wenn du Lücken allgemein als $-$ notierst, zumindest bei mir war es der Fall,
und deswegen habe ich bei der Notaion die Lückengrößen $\overline{G}$ und
$\overline{K}$ eingeführt. Also $\overline{G}$ steht für Lücke mit Größe des
Durchmessers von $G$, und entsprechend für $\overline{K}$.

 Aber wenn man darüber Übersicht behalten kann, ist
das natürlich nicht wichtig, mir hats zumindest geholfen.





StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6237
Herkunft: Milchstraße
 Beitrag No.24, eingetragen 2020-08-03 13:37    [Diesen Beitrag zitieren]

2020-08-03 06:43 - haribo in Beitrag No. 22 schreibt:
denn damit gehts bei n=4 doch in 6 zügen ?:
  1. GKGKGKGK
  2. GKGKG--KKG
  3. --GKG--KKGGK
  4. ----GGKKKGGK
  5. ----GGKKK--KGG
  6. ----GG--KKKKGG
  7. ----GGGGKKKK


Ich sehe hier zwei Macken. In Schritt 5 verschiebst du KK in eine Lücke, wo ehemals GG drin waren. Dadurch ist Luft zwischen den vier K*s. Ich sehe nicht, wie man die Luft weg bekommt. Im letzten Schritt schiebst du GG in eine KK-Lücke. Das ließe sich wie folgt auf Kosten eines zusätzlichen Schritts heilen.
  1. GKGKGKGK
  2. GKGKG--KKG
  3. --GKG--KKGGK
  4. ----GGKKKGGK
  5. ----GGKKK--KGG
  6. ----GG--KKKKGG
  7. ------GGKKKKGG
  8. ----GGGGKKKK


haribo
Senior
Dabei seit: 25.10.2012
Mitteilungen: 2575
Herkunft:
 Beitrag No.23, eingetragen 2020-08-03 12:32    [Diesen Beitrag zitieren]

2020-08-02 22:58 - StrgAltEntf in Beitrag No. 17 schreibt:
Ich habe noch keine gute Idee, wie man das 4-4-Problem mit Brute-Force angehen könnte.

als idee,
eine grössenverteilung wählen die nie falsche ergebnisse liefern könnte: 1+5


haribo
Senior
Dabei seit: 25.10.2012
Mitteilungen: 2575
Herkunft:
 Beitrag No.22, eingetragen 2020-08-03 06:43    [Diesen Beitrag zitieren]

dann funktioniert diese "GK" notation durchmessertechnisch auch nicht

denn damit gehts bei n=4 doch in 6 zügen ?:

GKGKGKGK
GKGKG - -KKG
 - -GKG - -KKGGK
 - - - -GGKKKGGK
 - - - -GGKKK - -KGG
 - - - -GG - -KKKKGG
 - - - -GGGGKKKK

vertrakt

haribo


viertel
Senior
Dabei seit: 04.03.2003
Mitteilungen: 27482
Herkunft: Hessen
 Beitrag No.21, eingetragen 2020-08-03 04:53    [Diesen Beitrag zitieren]

2020-08-03 02:10 - Robinsson in Beitrag No. 20 schreibt:
@viertel: dein 4-4-Algorithmus macht die Annahme, dass die große Münze genau doppelten Durchmesser der kleinen hat, oder? Ich beziehe mich auf drittletzen und vorletzten Schritte.
Nein, keine Annahme. Ich habe es einfach damit händisch durchprobiert.
Und falle tatsächlich auf die Nase, wenn ich die Radien ändere.
Also zurück in die Denkerwerkstatt …


Robinsson
Aktiv
Dabei seit: 15.07.2020
Mitteilungen: 21
Herkunft:
 Beitrag No.20, eingetragen 2020-08-03 02:10    [Diesen Beitrag zitieren]

@viertel: dein 4-4-Algorithmus macht die Annahme, dass die große Münze genau doppelten Durchmesser der kleinen hat, oder? Ich beziehe mich auf drittletzen und vorletzten Schritte.

Aber ich denke den kann man recht einfach retten:


Vor dem drittletzten Schritt haben wir:

$GGGGKKK\overline{GG}K$
 und dein Algorithmus macht weiter:

$GGGG\overline{G}KKK\overline{G}K$ <- da wird implizit Durchmesser G = 2*Durchmesser K verwendet.

Weiter folgt
$GGGG\overline{GG}KKKK$
$GGGGKKKK$

Ich würde einfach das so machen: shifte die beiden rechten direkt benachbarten $KK$ in
$GGGGKKK \overline{GG} K$ nach rechts zum ganz rechten $K$ zu $GGGK \overline{GG} KKK$ und
dann dasselbe mit $GK$-Paar links von $\overline{GG}$. Erhalten $GGG\overline{GG}GKKKK$ und der
Rest ist klar.


Robinsson
Aktiv
Dabei seit: 15.07.2020
Mitteilungen: 21
Herkunft:
 Beitrag No.19, eingetragen 2020-08-03 01:26    [Diesen Beitrag zitieren]

Wow dann geht das schon mal für 3-3 und 4-4.
Meine Idee zu n-n:

Wir starten mit $GKGK...GK$ wobei $G$ und $K$ jeweils n-mal vorkommt.

Dann lässt sich n eindeutig schreiben als $n= 3k + s$ mit $s=0,1,2$. Wir
spalten $GKGK...GK$ in kleinere 3-3 oder 4-4 Blöcke die "weit" genug
voneinander
entfernt werden können, damit wenn wir zunachst auf diese jeweils
separat den 3-3 oder 4-4-Algorithmus anwenden, ohne dass sie sich
jeweils in die Quere kommen.

Falls also $s=0$ , spalten wir  $GKGK...GK$ in $k$-viele 3-3-Blöcke
die durch ausreichend große Lücken voneinander getrennt werden können.

Falls $s=1$ spalten wir $GKGK...GK$ in $k-1$ viele 3-3-Blöcke
und ein 4-4-Block und falls $s=2$ in $k-2$ viele 3-3-Blöcke
und zwei 4-4-Blöcke.

Nach unseren jetzigen Erkenntnissen können wir 3-3-Block $GKGKGK$ zu
$GGGKKK$ transformieren und entsprechen den 4-4-Block, an dieser
Stelle großen Dank an viertel.

Jetzt bleibt die Frage, angenommen, wir haben zwei bereits fertige 3-3-
Blöcke von der Form
$GGGKKK$, die durch gewisse Lücke voneinander getrennt sind.
Können wir sie irgendwie zu einem super duper 6-6-Block
$GGGGGGKKKKKK$ verbauen?

Entsprechend könnte man natürlich fragen, ob 3-3 Block $GGGKKK$
mit 4-4 Block $GGGGKKKK$-Block zu einem 7-7-Block, und daselbe
mit zwei 4-4-Blöcken.

War nur eine Idee, man kann aber bestimmt in viele Richtungen denken.


viertel
Senior
Dabei seit: 04.03.2003
Mitteilungen: 27482
Herkunft: Hessen
 Beitrag No.18, eingetragen 2020-08-03 00:42    [Diesen Beitrag zitieren]
\(\begingroup\)\(\newcommand\d{\mathop{}\!\mathrm{d}}\)
Hier der 4-er:


Breitensuche:
Auf einem Level alle Zweierpäckchen an alle möglichen Positionen anbauen, d.h. das Päckchen darf nicht frei in die Wildnis gelegt werden.
Eine Konfiguration als Liste speichern: $|a_0|a_1|\dots|a_{2n-1}|$
Dabei ist $a_i$ einer der beiden Durchmesser $d_1$ oder $d_2$, oder die Breite $-b$ einer Lücke der Breite $b$. Das Blöde: die Liste muß für jede neue Konfiguration umgespeichert werden, Lücken müssen zusammengefaßt werden oder verschwinden.
Beispiel mit $d_1=1$, $d_2=2$:
$|1|2|1|2|1|2|1|2|$
$|1|2|1|2|1|-3|2|2|1|$
\(\endgroup\)

StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6237
Herkunft: Milchstraße
 Beitrag No.17, eingetragen 2020-08-02 22:58    [Diesen Beitrag zitieren]

Ich habe noch keine gute Idee, wie man das 4-4-Problem mit Brute-Force angehen könnte.

[Die Antwort wurde nach Beitrag No.15 begonnen.]


viertel
Senior
Dabei seit: 04.03.2003
Mitteilungen: 27482
Herkunft: Hessen
 Beitrag No.16, eingetragen 2020-08-02 22:57    [Diesen Beitrag zitieren]

Hatte ich schon vermutet 😎
Aber soooo schnell…


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6237
Herkunft: Milchstraße
 Beitrag No.15, eingetragen 2020-08-02 22:52    [Diesen Beitrag zitieren]

2020-08-02 22:39 - viertel in Beitrag No. 14 schreibt:
Immerhin ist es möglich, die Reihenfolge zu vertauschen:

Das geht aber auch etwas schneller ;-)
RWRW
R..WWR
RWW..R
..WRWR


viertel
Senior
Dabei seit: 04.03.2003
Mitteilungen: 27482
Herkunft: Hessen
 Beitrag No.14, eingetragen 2020-08-02 22:39    [Diesen Beitrag zitieren]

Immerhin ist es möglich, die Reihenfolge zu vertauschen:
OoOooOoO


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6237
Herkunft: Milchstraße
 Beitrag No.13, eingetragen 2020-08-02 18:27    [Diesen Beitrag zitieren]

2020-08-02 17:40 - Robinsson in Beitrag No. 11 schreibt:
Das Argument scheint logisch zu sein, aber mir viel zu unständlich.
Sieht jemand einen knapperen Grund wieso wir nicht $GKGK$ zu
$GGKK$ transformieren können? Oder eben dass es doch möglich ist und mein Argument ist falsch.

Ich habe jetzt nicht alles nachvollzogen, aber es scheint mir auch sehr umständlich zu sein. Ich bin sicher, dass es mit vier Münzen nicht möglich ist, habe aber auch kein schönes Argument. Außer: Wie man leicht sieht 😄 Es geht übrigens selbst dann nicht, wenn die Münzen den gleichen Durchmesser haben (aber ansonsten unterscheidbar sind), also kann man bei der Argumentation den Größenunterschied vernachlässigen.


Robinsson
Aktiv
Dabei seit: 15.07.2020
Mitteilungen: 21
Herkunft:
 Beitrag No.12, eingetragen 2020-08-02 17:49    [Diesen Beitrag zitieren]

@AlphaSigma: Hi, danke dir für die Referenz.
Hab die Aufgabe in der deutschen Fassung leider übersehen. Die Aufgabe
zu "Laubfröschen" habe ich gelesen und die Idee verstanden. Glaube ich zumindest. Aber wie ich das auf diese Situation anwende, habe ich nicht rausgefunden. Siehst du das? Die erlaubten Züge in beiden Aufgaben sind grundverscheiden. In Laubfrosch-Aufgabe wurde gesagt, dass es eine *notwendige* Bedingung ist um zur Lösung zu kommen die Züge so zu machen, dass die Farbe der Stöpsen in der Reihe nach jedem Zug immer alternieren muss. Danach richtete sich die Strategie, das verstehe ich. Wie überträgt sich das auf die Münzenverschiebung-Aufgabe? Gibts da auch eine notwendige Bedingung?

Ich habe im Beitrag 11 etwas umständlich gezeigt, dass der Fall mit 2 kleinen und 2 großen Münzen unlösbar scheint. Ich vermute, dass eine solche notwendige Bedingung nach der ich siche auch mein Beweis um einiges vereinfachen könnte.


Robinsson
Aktiv
Dabei seit: 15.07.2020
Mitteilungen: 21
Herkunft:
 Beitrag No.11, eingetragen 2020-08-02 17:40    [Diesen Beitrag zitieren]

Hallo Leute,

danke euch allen für die konstruktiven Beiträge. Ich bin zwischendurch
zur Erkenntnis gelangt, dass bei 2 kleinen und zwei großen Münzen
das Problem unlösbar ist. Ich verwende die Notation aus
Betrag Nr 2 mit den $K, G, \overline{K}, \overline{G}$:

Wenn wir mit $GKGK$ beginnen und alle möglichen Züge versuchen
zu untersuchen, machen wir ein Paar Beobachtungen:

1. oE hat jeder Zwischenschritt die Form $A_1 A_2 A_3 \overline{X} A_4$
oder $A_1 \overline{X} A_2 A_3 A_4$ mit $A_i \in \{K,G\}$ und $\bigcup_{i=1} ^4 A_i=\{G,G,K,K\}$. Das $\overline{X}$ ist eine Lücke als
Kombination der $\overline{K}, $ und $\overline{G}$. Begründung:
Züge wie zB $G \overline{KG} KGK \to G \overline{KG} K  \overline{KKKGG} GK$ sind redundant, da im nächsten
Zug sowieso *nur* $GK$ wieder bewegt werden kann.


2. Klar können wir *innerhalb* $\overline{X}$ die
$\overline{K}, $ und $\overline{G}$ untereinander beliebig vertauschen,
denn das ist nur eine Lücke zwischen $A_3$ und $A_4$
und es kommt nur auf Gesamtzahl der $\overline{K}, $ und $\overline{G}$
in $\overline{X}$ an, also zum Beispiel $\overline{X}= \overline{4K, 3G}$ oder so.


Dann komme ich durch ausprobieren zur Beobachtung, dass wenn wir mit
$GKGK$ starten und erlaubte Züge ausführen, nur folgende Konstellationen
für $A_1 A_2 A_3 \overline{X} A_4$ möglich sind

1. $KKG \overline{nK, mG} G$ mit $n,m$ ungerade bzw das gleiche
nur mit vertauschten $K$ und $G$

2. $KGG \overline{nK, mG} K$ wieder mit $n,m$ ungerade bzw das gleiche
nur mit vertauschten $K$ und $G$

3. $GKG \overline{nK, mG} K$ mit $n,m$ *gerade* bzw das gleiche
nur mit vertauschten $K$ und $G$

4. Entsprechend mit $A_1 \overline{X} A_2 A_3 A_4$ anstelle von
$A_1 A_2 A_3 \overline{X} A_4$


Machen wir nun Reverse Engeneering mit $GGKK$, so führt ein
legitimer Zug zu $G \overline{GK} KGK$. Da sind $n=m=1$ ungerade.
Also können wir nicht von Anfangskonstellation $GKGK$ hierhin
gelangen.

Das Argument scheint logisch zu sein, aber mir viel zu unständlich.
Sieht jemand einen knapperen Grund wieso wir nicht $GKGK$ zu
$GGKK$ transformieren können? Oder eben dass es doch möglich ist und mein Argument ist falsch.


thureduehrsen
Senior
Dabei seit: 13.11.2007
Mitteilungen: 857
Herkunft: Kiel, Deutschland
 Beitrag No.10, eingetragen 2020-08-02 17:07    [Diesen Beitrag zitieren]

2020-08-02 16:49 - viertel in Beitrag No. 8 schreibt:
Von der Aufgabe mit 6 gleichen Gläsern gibt es noch diese Variante:

Auf dem Tisch stehen nebeneinander 6 gleiche Gläser, abwechselnd gefüllt und leer.
Ändere die Reihenfolge, so daß die vollen und die leeren Gläser jeweils nebeneinander stehen. Mit einer einzigen(!) Aktion.


Wenn drei volle neben drei leeren Gläsern stehen, und die Aufgabe darin besteht, dass danach immer ein volles und ein leeres Glas sich abwechseln sollen: dann ist die Sache einfach:


Kippe den Inhalt des mittleren vollen Glases in das mittlere der leeren Gläser, dann stelle das nunmehr leere Glas an dieselbe Stelle zurück, von der du es aufgenommen hattest.


Deine Variante ist quasi die Umkehrfunktion dazu. Es fehlt eine kurze, knackige Beschreibung. 😎

mfg
thureduehrsen


AlphaSigma
Aktiv
Dabei seit: 23.11.2012
Mitteilungen: 222
Herkunft:
 Beitrag No.9, eingetragen 2020-08-02 16:52    [Diesen Beitrag zitieren]

Hallo,

nur zur Info: In der dt. Version "Mathematisch denken" 5. Aufl. ist das in Kapitel 10 "Aufgaben" die Aufgabe 32 (Münzenverschiebung) auf S. 185.
In der dt. Version steht zusätzlich der Hinweis: "Erinnert Sie das an Laubfrösche". Bei der Aufgabe "Laubfrösche" auf S. 59 in Kap. 3 stecken 5 schwarze Stöpsel links und 5 weiße Stöpsel rechts in einer Reihe von 11 Löchern. Ziel ist es die schwarzen und die weißen Stöpsel zu tauschen, wobei die schwarzen Stöpsel nur nach rechts und die weißen Stöpsel nur nach links bewegt werden dürfen.


[Die Antwort wurde nach Beitrag No.7 begonnen.]


viertel
Senior
Dabei seit: 04.03.2003
Mitteilungen: 27482
Herkunft: Hessen
 Beitrag No.8, eingetragen 2020-08-02 16:49    [Diesen Beitrag zitieren]
\(\begingroup\)\(\newcommand\d{\mathop{}\!\mathrm{d}}\)
Damit ist für $n=4$ der 7-Züger momentan die beste Lösung für unterschiedlich große Gläser/Münzen/xxx.

Von der Aufgabe mit 6 gleichen Gläsern gibt es noch diese Variante:

Auf dem Tisch stehen nebeneinander 6 gleiche Gläser, abwechselnd gefüllt und leer.
Ändere die Reihenfolge, so daß die vollen und die leeren Gläser jeweils nebeneinander stehen. Mit einer einzigen(!) Aktion.
\(\endgroup\)

StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6237
Herkunft: Milchstraße
 Beitrag No.7, eingetragen 2020-08-02 16:28    [Diesen Beitrag zitieren]

@viertel, @haribo:

Nein, mit unterschiedlichen Durchmessern funktioniert meine Lösung nicht - sonst hätte ich es nicht erwähnt, dass die Weingläser gleiche Größe haben.

Hier ist meine Lösung
  1. RRRRWWWW
  2. R..RWWWWRR
  3. RWWR..WWRR
  4. RWWRWRW..R
  5. ..WRWRWRWR



haribo
Senior
Dabei seit: 25.10.2012
Mitteilungen: 2575
Herkunft:
 Beitrag No.6, eingetragen 2020-08-02 16:01    [Diesen Beitrag zitieren]

Str, geht deine lösung denn auch mit verschiedengrossen gläsern?
haribo

[Die Antwort wurde nach Beitrag No.4 begonnen.]


viertel
Senior
Dabei seit: 04.03.2003
Mitteilungen: 27482
Herkunft: Hessen
 Beitrag No.5, eingetragen 2020-08-02 15:48    [Diesen Beitrag zitieren]

@StrgAltEntf
Funktioniert deine Lösung auch mit verschieden großen Steinen?
Denn bei gleichgroßen Steinen paßt in eine Lücke X..Y jede der Kombinationen AA, AB, BA und BB.
Bei unterschiedlichen Steinen kommt es auf die Größe der Lücke an, ob OO, Oo oder auch nur oo reinpaßt.


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6237
Herkunft: Milchstraße
 Beitrag No.4, eingetragen 2020-08-02 11:04    [Diesen Beitrag zitieren]

Hallo,

vor vielen Jahren habe ich ein ähnliches Rätsel kennengelernt. Statt um große und kleine Münzen ging es dabei um vier Rot- und vier Weißweingläser, die allerdings alle die gleiche Größe haben. Man kann das ganz gut mit vier schwarzen und vier weißen Gosteinen simulieren. Oder mit Smileys:

🙂🙂🙂🙂🙃🙃🙃🙃 \(\longrightarrow\) 🙃🙂🙃🙂🙃🙂🙃🙂

Um meine Freunde zu beeindrucken, hatte ich die Lösung (mit vier Zügen) auswendig gelernt. Niemand konnte es nachmachen 😁 Ich kann die Lösung bis heute.


viertel
Senior
Dabei seit: 04.03.2003
Mitteilungen: 27482
Herkunft: Hessen
 Beitrag No.3, eingetragen 2020-08-02 05:55    [Diesen Beitrag zitieren]

So:



Robinsson
Aktiv
Dabei seit: 15.07.2020
Mitteilungen: 21
Herkunft:
 Beitrag No.2, eingetragen 2020-08-02 03:25    [Diesen Beitrag zitieren]

Hi viertel,

wie kommst du im Fall n=3 auf drei Züge?

Ich versuche es mal mit folgendem Darstellungsschema & Notationen:

$K$ für kleine Münze, $G$ für größe M,
$\overline{K}$ für Lücke in der Reihe von der Größe der kleinen Münze,
$\overline{G}$  Lücke in der Reihe von der Größe der großen Münze.

Wir starten also mit $GKGKGK$.

Wenn wir zum Beispiel das Paar $KG$ auf Position 23 rausnehmen und es im Abstand
$\overline{GGKKK}$ rechts vom ganz rechtem $K$ platzieren, dann sieht das ergebnis
so aus:

$G \overline{KG} KGK \overline{GGKKK} KG$.

Könntest du mit diesem Schema (hab kein einfacheres gefunden) skizzieren,
wie du auf nur drei Züge bei n=3 kommst?


viertel
Senior
Dabei seit: 04.03.2003
Mitteilungen: 27482
Herkunft: Hessen
 Beitrag No.1, eingetragen 2020-08-02 03:10    [Diesen Beitrag zitieren]
\(\begingroup\)\(\newcommand\d{\mathop{}\!\mathrm{d}}\)
Hi Robinsson

Die Fälle $n=3$ (3 Züge) und $n=4$ (7 Züge, geht vielleicht besser) sind gelöst.
Aber ein Schema habe ich dafür noch nicht.

Gruß vom ¼
\(\endgroup\)

Robinsson
Aktiv
Dabei seit: 15.07.2020
Mitteilungen: 21
Herkunft:
 Themenstart: 2020-08-01 22:30    [Diesen Beitrag zitieren]

Guten Abend,

ich arbeite seit dieser Woche das nette Büchlein "Thinking Mathematically" by Mason, Burton and Stacey durch. dazu gibts nebenbei bemerkt auch deutsche Fassung, aber die Aufgabe, die mir grad Kopfzerbrechen bereitet ist nur in der englischen F. zu finden. Die gemeinte Aufgabe ist auf seite 149 zu finden. Hier im Original-Wortlaut:





Ein einzelner legitimer Zug ist demnach genau solcher, bei dem genau zwei benachbarte Münzen als Paar bewegt werden können. Wohin ist egal, hauptsache andere Münzen werden nicht bewegt und das Paar "trennt sich nicht voneinander". Als Beispiele für legitime Züge lohnt es ein Blick  hierhin bei der  Lösung von Aufgabe 7 zu werfen.


Mir ist gelungen das Problem bei Vereinfachungen mit 2 kleinen und 2 großen Münzen bzw 2 kleinen und 3 großen (das ist genau das verlinkte Puzzle 7) zu lösen. Aber das war eher try and error Lösung und hat mich nicht zu eine allgemeineren tiefgründigen Strategie geführt wie ich im 3-3 oder allgemeiner n-n-Fall vorgehen könnte. Ich bin mir sicher wenn ich mehr getüftelt hätte, könnte ich auch durch ausprobieren das Anfangsproblem mit 3 kleinen und 3 großen Münzen lösen, aber irgendwie erkenne ich nicht eine tiefere Strategie dahinter, die auch auf Verallgemeinerung des Problems anwendbar sein könnte mit
 n kleinen und n großen Münzen alternierend angeordnet für n beliebige natürliche Zahl. Also so eine Strategie, die man als eine Art Algorithmus in Pseudocode runterscheiben könnte, wahrscheinlich sowas rekursives. Hab zuerst an ein Algeorithmus mit Rekursion gedacht, der ähnlich gestrickt wie für "Türme von Hanoi" ist. Sicher komplizierter, der aber irgendwo eine Routine enthält, die mit Rekursion auf das Problem mit kleinerem n reduziert.




 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]