Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Kombinatorik & Graphentheorie » Rätsel mit Münzen verschieben aus "Thinking Mathematically"
Druckversion
Druckversion
Antworten
Antworten
Seite 1   [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  Themenstart: 2020-08-01


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.





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: 27458
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-08-02

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


-----------------
Bild
\(\endgroup\)


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.2, vom Themenstarter, eingetragen 2020-08-02


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?



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: 27458
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-08-02


So:




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6154
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-08-02


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.



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: 27458
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2020-08-02


@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.



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: 2537
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2020-08-02


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

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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6154
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2020-08-02


@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




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: 27458
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2020-08-02

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


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
AlphaSigma
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.11.2012
Mitteilungen: 213
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2020-08-02


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.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 799
Aus: Kiel, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2020-08-02


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



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.11, vom Themenstarter, eingetragen 2020-08-02


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.



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.12, vom Themenstarter, eingetragen 2020-08-02


@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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6154
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2020-08-02


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.



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: 27458
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, eingetragen 2020-08-02


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6154
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2020-08-02


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



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: 27458
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, eingetragen 2020-08-02


Hatte ich schon vermutet 😎
Aber soooo schnell…



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6154
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2020-08-02


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.]



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: 27458
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, eingetragen 2020-08-03

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


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.19, vom Themenstarter, eingetragen 2020-08-03


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.



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.20, vom Themenstarter, eingetragen 2020-08-03


@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.



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: 27458
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.21, eingetragen 2020-08-03


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 …



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: 2537
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.22, eingetragen 2020-08-03


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



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: 2537
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.23, eingetragen 2020-08-03


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6154
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.24, eingetragen 2020-08-03


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



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.25, vom Themenstarter, eingetragen 2020-08-03


@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.






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.26, vom Themenstarter, eingetragen 2020-08-03


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?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6154
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.27, eingetragen 2020-08-03


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.



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.28, vom Themenstarter, eingetragen 2020-08-03


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.



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: 2537
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.29, eingetragen 2020-08-03


#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




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6154
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.30, eingetragen 2020-08-03


@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.



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: 2537
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.31, eingetragen 2020-08-03


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!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1793
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.32, eingetragen 2020-08-03


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 



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: 2537
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.33, eingetragen 2020-08-03


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6154
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.34, eingetragen 2020-08-03


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1793
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.35, eingetragen 2020-08-03

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


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: 2537
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.36, eingetragen 2020-08-03


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,











Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6154
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.37, eingetragen 2020-08-03


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?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1793
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.38, eingetragen 2020-08-03


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.



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.39, vom Themenstarter, eingetragen 2020-08-08


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$.





Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
-->> Fortsetzung auf der nächsten Seite -->>
Seite 1Gehe 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]