Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Kombinatorik & Graphentheorie » Rätsel mit Münzen verschieben aus "Thinking Mathematically"
Thema eröffnet 2020-08-01 22:30 von Robinsson
Druckversion
Druckversion
Antworten
Antworten
Seite 2   [1 2]   2 Seiten
Autor
Universität/Hochschule Rätsel mit Münzen verschieben aus "Thinking Mathematically"
Robinsson
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 15.07.2020
Mitteilungen: 21
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.40, vom Themenstarter, eingetragen 2020-08-08


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.







Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6554
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.41, eingetragen 2020-08-10


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?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Robinsson
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 15.07.2020
Mitteilungen: 21
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.42, vom Themenstarter, eingetragen 2020-08-11


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?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2546
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.43, eingetragen 2020-08-12


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6554
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.44, eingetragen 2020-08-12


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?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 27460
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.45, eingetragen 2020-08-12

\(\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\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2546
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.46, eingetragen 2020-08-12


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 27460
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.47, eingetragen 2020-08-12

\(\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\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2546
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.48, eingetragen 2020-08-12


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Robinsson hat die Antworten auf ihre/seine Frage gesehen.
Seite 2Gehe zur Seite: 1 | 2  
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
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]