Matroids Matheplanet Forum Index
Moderiert von matroid
Matroids Matheplanet Forum Index » Matheplanet » Spektrum-Krawattenrätsel
Seite 1   [1 2 3 4 5]   5 Seiten
Autor
Kein bestimmter Bereich Spektrum-Krawattenrätsel
matroid
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.03.2001
Mitteilungen: 14519
Wohnort: Solingen
  Themenstart: 2008-08-15

Arbeitsraum für das Spektrum-Krawattenrätsel Viel Spaß und Erfolg!


   Profil
krischi
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 09.06.2007
Mitteilungen: 813
  Beitrag No.1, eingetragen 2008-08-15

Meine Vermutung: n*(n-1) Mein Weg: Zuerst würde ich die beiden Bälle aus 1 und 2, dann aus 2 und 3, usw. tauschen, bis die beiden Bälle n in Fach n liegen. Dafür benötige ich 2*(n-1) Züge. Dann würde ich den Voegang wiederholen, indem ich die Bälle von Fach 1 bis Fach n-1 tausche. 2*(n-2) weitere Züge. So würde ich dann fortfahren, bis ich nur noch 2*1 mal in den Fächern 1 und 2 vertauschen müsste. Ich hätte also \ 2*sum(k,k=1,n-1)=2*(n*(n-1))/2=n*(n-1) Züge gemacht. Ich hab jetzt aber noch nicht den Nachweis, dass das die schnellste Vorgehensweise ist, weil ich mich dafür noch nicht lange genug mit dem Thema beschäftigt habe; allerdings wüstte ich keinen besseren Weg... Vielleicht kann ja jemand meine Zuganzahl unterbieten...?


   Profil
Ex_Senior
  Beitrag No.2, eingetragen 2008-08-15

Hallo Krischi! Deine Lösung bietet eine (schon bekannte) obere Schranke. Siehe dazu die Diskussion in den Kommentaren zum Artikel, der dieses Problem vorstellt. Es geht aber besser. In den Hinweisen auf den Internet-Seiten des Rätsels ist eine kürzere Lösung für n=5 konkret angegeben. Grüße, Cyrix


   Profil
valentin
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.03.2005
Mitteilungen: 1478
Wohnort: Berlin
  Beitrag No.3, eingetragen 2008-08-15

Hallo krischi, lies doch bitte erst mal durch, was in den 23 Kommentaren zum Artikel schon geschrieben wurde. Ich verweise insbesondere auf die Zahlenfolge 0, 2, 5, 10, 15, 23, 31 -- Valentin [Die Antwort wurde nach Beitrag No.1 begonnen.]


   Profil
krischi
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 09.06.2007
Mitteilungen: 813
  Beitrag No.4, eingetragen 2008-08-15

Ah OK, hab ich nicht gesehen... eek Schade eigentlich...


   Profil
valentin
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.03.2005
Mitteilungen: 1478
Wohnort: Berlin
  Beitrag No.5, eingetragen 2008-08-15

So, mit Brute Force habe ich folgende optimalen Schrittzahlen ermittelt: n=7: 31 n=8: 40 kann jemand das nochmal bestätigen, um etwaige Programmierfehler auszuschliessen? Dann könnte man diese Zahlen auch irgendwann mal offiziell bei der On-Line Encyclopedia of Integer Sequences eintragen. n=9 sollte mit meinem Programm machbar sein, wenn man etwa 360 Gigabyte Speicher und einige Monate Laufzeit einplant... -- Valentin


   Profil
gaussmath
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 16.06.2007
Mitteilungen: 9044
Wohnort: Hannover
  Beitrag No.6, eingetragen 2008-08-15

Hallo valentin, würde es Dir was ausmachen, Deinen Code zu posten? gaussmath


   Profil
valentin
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.03.2005
Mitteilungen: 1478
Wohnort: Berlin
  Beitrag No.7, eingetragen 2008-08-15

Prinzipiell nicht. Aber ich will mein Ergebnis erstmal bestätigt sehen... -- Valentin


   Profil
valentin
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.03.2005
Mitteilungen: 1478
Wohnort: Berlin
  Beitrag No.8, eingetragen 2008-08-15

Ich kann ja sagen, was ich gemacht habe: Breitensuche durch den Zustandsraum. Nur um mal darzulegen, wie die Komplexität wächst: \sourceon N Zustände 2 3 3 21 4 282 5 6210 6 202410 7 9135630 8 545007960 \sourceoff schätzungsweise wird es bei N=9 etwa 45 Milliarden Zustände geben. -- Valentin


   Profil
Realshaggy
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.03.2008
Mitteilungen: 1293
  Beitrag No.9, eingetragen 2008-08-15

Eine naheliegende Vermutung wäre imho \ a_1=0 a_n=(2n-1)n/3   für n==0,2 mod 3 a_n=((2n-1)n+2)/3  für n==1 mod 3, n>1 Ich kann leider den in den Kommentaren angegebenen Beweis nich völlig nachvollziehen, schon die Definition, was so ein "Fehlstand" ist, ist irgendwie so komisch geschrieben, dass ich nich genau weiß, was gemeint ist. Gibts da irgendeinen Link dazu? Die Methode scheint ja ähnlich zu dem zu sein, was man schon in der linearen Algebra bei der Einführung von geraden/ungeraden Permutationen vor der Leibnizschen Determinantenformel macht. Eventuell kann man ja eine untere Schranke konstruieren, und dann eine Lösung angeben, die diese Schranke realisiert. Was habt ihr außer Breitensuche für heuristischen Methoden zum finden "guter" Lösungen verwendet? Die auf der Homepage angegebene Lösung für n=5 sieht sehr symmetrisch aus, läßt die sich auf höhere n hochziehen, zumindest für einige n? Edit: Vergesst meinen Vorschlag, ich zieh mich aus der aufgabe zurück, und geh nochmal das kleine Einmaleins üben. 11*6/3 ist definitiv nicht 23  biggrin Edit2: Nachwas, wenn eh schon jemand eine Breitensuche implementiert hat, könnt ihr dann eventuell auch angeben, wieviele Lösungen es gibt, und wie diese Aussehen? Dabei würde mich vor allem erstmal der Fall n=6 interessieren, in dem ja irgendwas "schiefzugehen" scheint in dem Sinne, dass man plötzlich nochmal eine Vertauschung mehr benötigt, als in der bewiesenen unteren Schranke. [ Nachricht wurde editiert von Realshaggy am 15.08.2008 18:02:03 ]


   Profil
Realshaggy
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.03.2008
Mitteilungen: 1293
  Beitrag No.10, eingetragen 2008-08-15

So, ich hab nohc ein bißchen rumprobiert. Ich habe mir versucht, irgendeine Systematik aus der Musterlösung für n=5 rauszuschauen, aber damit komme ich für n=8 auch nur auf einen Wert von 42, was größer ist als die vermutlich optimalen 40. Jetzt muß ich wohl wirklich mit programmieren anfangen. Hauptsächlich interessiert mich erstmal, wieviele Lösungen es jeweils gibt, und ob darunter welche sind, die irgendwelche Systematiken erkennen lassen. Ich weiß nur nicht, was genau valentin mit "Breitensuche im Zustandsraum" meint. Im Prinzip sind ja nicht Zustände gesucht, sondern Pfade auf dem Zustandsraum mit vorgegebenem Anfangs- und Endzustand und möglichst kurzer Länge. [ Nachricht wurde editiert von Realshaggy am 15.08.2008 20:27:58 ]


   Profil
valentin
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.03.2005
Mitteilungen: 1478
Wohnort: Berlin
  Beitrag No.11, eingetragen 2008-08-15

Noch fürs Logbuch: Ich hab die Zustandsmenge für N=9 durchgezählt ... solange man das nicht speichern muss, geht das in einigen Stunden. \sourceon N Zustände 1 1 2 3 3 21 4 282 5 6210 6 202410 7 9135630 8 545007960 9 41514583320 \sourceoff Also sieht es mit 41 Milliarden sogar minimal besser aus als in meiner Schätzung. -- Valentin


   Profil
valentin
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.03.2005
Mitteilungen: 1478
Wohnort: Berlin
  Beitrag No.12, eingetragen 2008-08-15

Hallo Realshaggy, \quoteon(2008-08-15 20:25 - Realshaggy in Beitrag No. 10) Hauptsächlich interessiert mich erstmal, wieviele Lösungen es jeweils gibt, und ob darunter welche sind, die irgendwelche Systematiken erkennen lassen. \quoteoff Leider gibt Breitensuche sowas nicht her. Es sollte aber viele Millionen verschiedene Lösungen der Länge 40 geben. \quoteon(2008-08-15 20:25 - Realshaggy in Beitrag No. 10) Ich weiß nur nicht, was genau valentin mit "Breitensuche im Zustandsraum" meint. Im Prinzip sind ja nicht Zustände gesucht, sondern Pfade auf dem Zustandsraum mit vorgegebenem Anfangs- und Endzustand und möglichst kurzer Länge. \quoteoff Genau solche Pfade liefert die Breitensuche ja. Allerdings scheint es es so, dass der Zielzustand den maximalen Abstand zum Anfangszustand hat, d.h. es gibt keinen Zustand, für den man mehr Vertauschungen braucht (dies müßte ich noch mal explizit verifizieren, aber da ich immer 99% der Zustände in der Suche ausgemustert hatte scheint es wirklich so zu sein). -- Valentin


   Profil
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1415
Wohnort: Koblenz (früher: Berlin)
  Beitrag No.13, eingetragen 2008-08-15

Ich denke, eine untere Schranke für die Zahl der Zustände dürfte (2n)!/2^2n sein. Der reale Wert scheint davon auch nicht weit entfernt zu sein. Kay [Die Antwort wurde nach Beitrag No.11 begonnen.]


   Profil
cow_gone_mad
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 11.01.2004
Mitteilungen: 6651
  Beitrag No.14, eingetragen 2008-08-15

Nur mal aus Interesse, und es sollte nicht so aufwendig sein. Sind die Minimizer eindeutig? Falls, jemand es ueberprueft. Danke smile LG, cow_ [Die Antwort wurde nach Beitrag No.12 begonnen.]


   Profil
matroid
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.03.2001
Mitteilungen: 14519
Wohnort: Solingen
  Beitrag No.15, vom Themenstarter, eingetragen 2008-08-15

Vielleicht kann man ja auch was übers Problem lernen, wenn man es mit 3 statt 2 Kugeln in jedem Fach untersucht.


   Profil
valentin
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.03.2005
Mitteilungen: 1478
Wohnort: Berlin
  Beitrag No.16, eingetragen 2008-08-15

Hallo Kay, ich bin mit anderen Überlegungen auf die obere Schranke von \ ((n!)^2)/2 + n gekommen. Damit haben wir es ja recht gut gesandwitched... @Cow: Was meinst du mit minimizer? -- Valentin [Die Antwort wurde nach Beitrag No.14 begonnen.] [ Nachricht wurde editiert von valentin am 15.08.2008 21:19:10 ]


   Profil
cow_gone_mad
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 11.01.2004
Mitteilungen: 6651
  Beitrag No.17, eingetragen 2008-08-15

@Valentin: Minimizer = Jede Art zu ziehen mit einer moeglichst kleinen Schrittzahl. LG, cow_


   Profil
valentin
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.03.2005
Mitteilungen: 1478
Wohnort: Berlin
  Beitrag No.18, eingetragen 2008-08-15

Wie ich oben bereits geschrieben habe, sollte es sehr viele verschiedene Lösungen geben. -- Valentin


   Profil
Realshaggy
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.03.2008
Mitteilungen: 1293
  Beitrag No.19, eingetragen 2008-08-15

Ah, jetzt hab ich das Prinzip verstanden, du berechnest für jeden Zustand seinen minimalen Abstand (Abstand = Anzahl der Züge die zur Überführung benötigt werden) vom Anfangszustand, indem du erst alle Zustände mit Abstand 1 suchst, dann alle mit Abstand 2 usw. [Die Antwort wurde nach Beitrag No.17 begonnen.]


   Profil
valentin
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.03.2005
Mitteilungen: 1478
Wohnort: Berlin
  Beitrag No.20, eingetragen 2008-08-15

\quoteon(2008-08-15 21:30 - Realshaggy in Beitrag No. 19) Ah, jetzt hab ich das Prinzip verstanden, du berechnest für jeden Zustand seinen minimalen Abstand (Abstand = Anzahl der Züge die zur Überführung benötigt werden) vom Anfangszustand, indem du erst alle Zustände mit Abstand 1 suchst, dann alle mit Abstand 2 usw. \quoteoff Korrekt. Ich denke, um die Topologie dieses Zustandsgraphen besser zu verstehen, lohnt es sich mal die Zustände zu einem Abstand k anzusehen und nach interessanten Invarianten zu suchen... -- Valentin


   Profil
Realshaggy
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.03.2008
Mitteilungen: 1293
  Beitrag No.21, eingetragen 2008-08-15

Die optimalen Lösungen liegen ja bisher immer haarscharf an der angegebenen unteren Schranke (bisher wird nur für n=6 eine Vertauschung mehr benötigt). Damit könnte man ein Programm erheblich beschleunigen, wenn man sich nochmal den in den Kommentaren geposteten Beweis ansieht, und von einem Zustand ausgehend zum nächsten Zustand nur solche Vertauschungen zuläßt, die die Anzahl der dort beschriebenen Inversionen verringern. Besser gesagt, man läßt nur sloche Tauschvorgänge zu, in denen auf der Kugel, die ein Fach nach rechts wandert, die größere Zahl steht. Damit spart man den größten Teil des Zustandsraumes aus, hat zwar zunächst keinen Beweis mehr, dass man die Länge einer optimalen Lösung erwischt, aber imho wesentlich bessere obere Schranken als bisher. [ Nachricht wurde editiert von Realshaggy am 15.08.2008 23:12:17 ]


   Profil
valentin
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.03.2005
Mitteilungen: 1478
Wohnort: Berlin
  Beitrag No.22, eingetragen 2008-08-15

Wow Kann das mir jemand erklären? -- Valentin


   Profil
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1415
Wohnort: Koblenz (früher: Berlin)
  Beitrag No.23, eingetragen 2008-08-16

Sehr Interessant; ich dachte eigentlich, die Zahlen könnte man mit einfacher Kombinatorik erhalten - weit gefehlt. Unter gelabelten 2-regulären Pseudodigraphen kann ich mir jetzt aber nichts vorstellen.. Vielleicht hier noch ein Link: http://www.math.rutgers.edu/~zeilberg/tokhniot/oBipartite Zitat: "... the enumerating sequence for n by n matrices with all the row-sums and column-sums equal to 2 and the entries are non-negative integers <= 2" Ist aber auch klar: jede Spalte entspricht einem Fach und die Bälle entsprechen den pro Spalte gesetzten Einsen. Und pro Zeile gibt es genau zwei Einsen, da jede Ball-Nr. genau zweimal vorkommt. Kay


   Profil
valentin
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.03.2005
Mitteilungen: 1478
Wohnort: Berlin
  Beitrag No.24, eingetragen 2008-08-16

\quoteon(2008-08-16 00:13 - Kay_S in Beitrag No. 23) Unter gelabelten 2-regulären Pseudodigraphen kann ich mir jetzt aber nichts vorstellen.. \quoteoff Ein gerichteter Graph mit Ausgangs- und Eingangsgrad 2, bei dem Schleifen und Doppelkanten erlaubt sind. \quoteon(2008-08-16 00:13 - Kay_S in Beitrag No. 23) Zitat: "... the enumerating sequence for n by n matrices with all the row-sums and column-sums equal to 2 and the entries are non-negative integers <= 2" \quoteoff Stimmt, war mal wieder viel einfacher, als ich gedacht habe. -- Valentin


   Profil
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1415
Wohnort: Koblenz (früher: Berlin)
  Beitrag No.25, eingetragen 2008-08-16

\quoteon(2008-08-16 00:20 - valentin in Beitrag No. 24) Ein gerichteter Graph mit Ausgangs- und Eingangsgrad 2, bei dem Schleifen und Doppelkanten erlaubt sind. \quoteoff Die Erklärung sieht dann vielleicht so aus: Die Knoten entsprechen den Fächern, die Ausgangskanten führen zu denjenigen Knoten, deren Nummern identisch mit denen der beiden Bälle ist. Damit ist auch der Eingangsgrad genau zwei, da es zu jeder Nummer genau zwei Bälle gibt. Eine Doppelkante bedeutet zwei gleichbeschriftete Bälle im Fach und eine Schleife bedeutet, Fach-Nr. und Ball-Nr. sind gleich. Kay


   Profil
valentin
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.03.2005
Mitteilungen: 1478
Wohnort: Berlin
  Beitrag No.26, eingetragen 2008-08-16

\quoteon(2008-08-16 00:20 - ich selbst in Beitrag No. 24) \quoteon(2008-08-16 00:13 - Kay_S in Beitrag No. 23) Unter gelabelten 2-regulären Pseudodigraphen kann ich mir jetzt aber nichts vorstellen.. \quoteoff Ein gerichteter Graph mit Ausgangs- und Eingangsgrad 2, bei dem Schleifen und Doppelkanten erlaubt sind. \quoteoff \ Auch hier gibt es den einfachen Zusammenhang zu den Matrizen: Betrachte die Matrix A, bei der A_ij die Anzahl der gerichteten Kanten von i nach j zählt. -- Valentin [Die Antwort wurde nach Beitrag No.24 begonnen.]


   Profil
Realshaggy
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.03.2008
Mitteilungen: 1293
  Beitrag No.27, eingetragen 2008-08-16

Kann denn jemand eine  Lösung für n=8 mit 40 Zügen angeben? Ich habe viele verschiedene Möglichkeiten probiert, und komme meist auf 42, aber nie darunter. Außerdem lohnt sich wahrscheinlich die Suche nach weiteren Invarianten, bei mir hat zum Beispiel jede Lösung von n=8 eine gerade Zahl von Zügen, wofür ich im Augenblick auch noch keine Begründung habe. [ Nachricht wurde editiert von Realshaggy am 16.08.2008 04:15:29 ]


   Profil
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1415
Wohnort: Koblenz (früher: Berlin)
  Beitrag No.28, eingetragen 2008-08-16

Ich würde folgende Formel vorschlagen (diese unterstellt ein einfaches quadratisches Wachstum): \ a_n = cases(5/8 (n^2-1), falls n ungerade;5/8 n^2+n/4-1, falls n gerade) Das ergibt die Folge 0, 2, 5, 10, 15, 23, 30, 41, 50, 64, 75, 92, ... Sollte tatsächlich für n=8 eine Lösung in 40 Zügen existieren, so stimmt das natürlich nicht mehr. Daher wäre ich auch mal an der 40er Lösung interessiert. Kay


   Profil
Mentat
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 13.04.2005
Mitteilungen: 321
Wohnort: Heidelberg
  Beitrag No.29, eingetragen 2008-08-16

Hallo, eventuell kann man noch folgende Größe einführen: Sei N die Anzahl der Fächer und m die Anzahl der bereits durchgeführten Züge (Vertauscheungen. Sei dann D(N,m) die Summe der Abstände aller Kugeln zum Zielfach. Im Fall N=3 und m=0 ist das 8, im ersten Fach liegen die dreien, die haben Abstand 2 zum dritten Fach, die zweien liegen bereits an der richtigen Stelle, die einsen haben den Abstand 2 zum ersten Fach. Betrachten wir jetzt, was passiert, wenn man einen Zug durchführt. Zwei Kugeln rücken jeweils näher an ihr Zielfach heran oder entfernen sich von diesem. Das heisst, D(N,m+1)\in {D(N,m),D(N,m)-2,D(N,m)+2}, die Summe aller Abstände ändert sich also pro Zug um 2 oder bleibt konstant. Da im Endzustand D(N,m_end)=0 sein muss und da jeder Zug D nur höchstens um 2 verringern kann, ist D(N,0)/2 eine untere Schranke für die Anzahl der Züge. D(N,0) lässt sich berechnen: D(N,0)=2*\sum(\|(N-j+1)-j\|,j=1,N) =2*(\sum(N+1-2j,0<2j=2j>N+1)). Der Fall 2j=N+1 trägt natürlich nichts bei. Also gilt D(N,0)/2= \sum(N+1-2j,0<2j=2j>N+1) (Substituiere in der zweiten Summe j^~=N+1-j) =2*\sum(N+1-2j,0<2j[Die Antwort wurde nach Beitrag No.27 begonnen.] [ Nachricht wurde editiert von Mentat am 16.08.2008 13:23:57 ]


   Profil
Master_John
Neu Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 15.08.2008
Mitteilungen: 1
  Beitrag No.30, eingetragen 2008-08-16

Hallo Kay_S, leider kann Deine Formel nicht stimmen. Denn für genügend große n sind die Folgeglieder Deiner Folge kleiner als die bekannte untere Schranke ceil(1/3*n(2n-1)) Etwa für n=7. Ich wäre auch an der Lösung 40 für n=8 interessiert. Ich brauche mindestens 41 Züge. Gruß, Markus [Die Antwort wurde nach Beitrag No.28 begonnen.]


   Profil
valentin
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.03.2005
Mitteilungen: 1478
Wohnort: Berlin
  Beitrag No.31, eingetragen 2008-08-16

Da hier ja ein reges interesse an optimalen Lösungen besteht, hier jeweils eine kürzeste Lösung für n=7 und n=8. Man erkennt eine gewisse Ähnlichkeit von beiden, allerdings mag dies auch ein Artefakt der Breitensuche sein. \sourceon 0        | 7 7 | 6 6 | 5 5 | 4 4 | 3 3 | 2 2 | 1 1 | 1        | 7 7 | 6 6 | 5 5 | 4 4 | 2 3 | 2 3 | 1 1 | 2        | 7 7 | 6 6 | 4 5 | 4 5 | 2 3 | 2 3 | 1 1 | 3        | 7 7 | 6 6 | 4 5 | 2 4 | 3 5 | 2 3 | 1 1 | 4        | 7 7 | 4 6 | 5 6 | 2 4 | 3 5 | 2 3 | 1 1 | 5        | 7 7 | 4 6 | 2 5 | 4 6 | 3 5 | 2 3 | 1 1 | 6        | 7 7 | 4 6 | 2 5 | 3 4 | 5 6 | 2 3 | 1 1 | 7        | 7 7 | 4 6 | 2 5 | 3 4 | 2 5 | 3 6 | 1 1 | 8        | 4 7 | 6 7 | 2 5 | 3 4 | 2 5 | 3 6 | 1 1 | 9        | 4 7 | 2 6 | 5 7 | 3 4 | 2 5 | 3 6 | 1 1 | 10       | 4 7 | 2 6 | 3 5 | 4 7 | 2 5 | 3 6 | 1 1 | 11       | 4 7 | 2 6 | 3 5 | 2 4 | 5 7 | 3 6 | 1 1 | 12       | 4 7 | 2 6 | 3 5 | 2 4 | 3 5 | 6 7 | 1 1 | 13       | 4 7 | 2 6 | 3 5 | 2 4 | 3 5 | 1 6 | 1 7 | 14       | 2 4 | 6 7 | 3 5 | 2 4 | 3 5 | 1 6 | 1 7 | 15       | 2 4 | 3 6 | 5 7 | 2 4 | 3 5 | 1 6 | 1 7 | 16       | 2 4 | 3 6 | 2 5 | 4 7 | 3 5 | 1 6 | 1 7 | 17       | 2 4 | 3 6 | 2 5 | 3 4 | 5 7 | 1 6 | 1 7 | 18       | 2 4 | 3 6 | 2 5 | 3 4 | 1 5 | 6 7 | 1 7 | 19       | 2 4 | 3 6 | 2 5 | 3 4 | 1 5 | 1 6 | 7 7 | 20       | 2 4 | 2 3 | 5 6 | 3 4 | 1 5 | 1 6 | 7 7 | 21       | 2 4 | 2 3 | 3 5 | 4 6 | 1 5 | 1 6 | 7 7 | 22       | 2 4 | 2 3 | 3 5 | 1 4 | 5 6 | 1 6 | 7 7 | 23       | 2 4 | 2 3 | 3 5 | 1 4 | 1 5 | 6 6 | 7 7 | 24       | 2 4 | 2 3 | 1 3 | 4 5 | 1 5 | 6 6 | 7 7 | 25       | 2 4 | 2 3 | 1 3 | 1 4 | 5 5 | 6 6 | 7 7 | 26       | 2 2 | 3 4 | 1 3 | 1 4 | 5 5 | 6 6 | 7 7 | 27       | 2 2 | 1 3 | 3 4 | 1 4 | 5 5 | 6 6 | 7 7 | 28       | 2 2 | 1 3 | 1 3 | 4 4 | 5 5 | 6 6 | 7 7 | 29       | 2 2 | 1 1 | 3 3 | 4 4 | 5 5 | 6 6 | 7 7 | 30       | 1 2 | 1 2 | 3 3 | 4 4 | 5 5 | 6 6 | 7 7 | 31       | 1 1 | 2 2 | 3 3 | 4 4 | 5 5 | 6 6 | 7 7 | \sourceoff \sourceon 0        | 8 8 | 7 7 | 6 6 | 5 5 | 4 4 | 3 3 | 2 2 | 1 1 | 1        | 8 8 | 7 7 | 5 6 | 5 6 | 4 4 | 3 3 | 2 2 | 1 1 | 2        | 8 8 | 7 7 | 5 6 | 4 5 | 4 6 | 3 3 | 2 2 | 1 1 | 3        | 8 8 | 7 7 | 5 6 | 4 5 | 3 4 | 3 6 | 2 2 | 1 1 | 4        | 8 8 | 5 7 | 6 7 | 4 5 | 3 4 | 3 6 | 2 2 | 1 1 | 5        | 8 8 | 5 7 | 4 6 | 5 7 | 3 4 | 3 6 | 2 2 | 1 1 | 6        | 8 8 | 5 7 | 4 6 | 3 5 | 4 7 | 3 6 | 2 2 | 1 1 | 7        | 8 8 | 5 7 | 4 6 | 3 5 | 3 4 | 6 7 | 2 2 | 1 1 | 8        | 8 8 | 5 7 | 4 6 | 3 5 | 3 4 | 2 6 | 2 7 | 1 1 | 9        | 5 8 | 7 8 | 4 6 | 3 5 | 3 4 | 2 6 | 2 7 | 1 1 | 10       | 5 8 | 4 7 | 6 8 | 3 5 | 3 4 | 2 6 | 2 7 | 1 1 | 11       | 5 8 | 4 7 | 3 6 | 5 8 | 3 4 | 2 6 | 2 7 | 1 1 | 12       | 5 8 | 4 7 | 3 6 | 3 5 | 4 8 | 2 6 | 2 7 | 1 1 | 13       | 5 8 | 4 7 | 3 6 | 3 5 | 2 4 | 6 8 | 2 7 | 1 1 | 14       | 5 8 | 4 7 | 3 6 | 3 5 | 2 4 | 2 6 | 7 8 | 1 1 | 15       | 5 8 | 4 7 | 3 6 | 3 5 | 2 4 | 2 6 | 1 7 | 1 8 | 16       | 5 8 | 4 7 | 3 6 | 2 3 | 4 5 | 2 6 | 1 7 | 1 8 | 17       | 5 8 | 3 4 | 6 7 | 2 3 | 4 5 | 2 6 | 1 7 | 1 8 | 18       | 5 8 | 3 4 | 2 6 | 3 7 | 4 5 | 2 6 | 1 7 | 1 8 | 19       | 3 5 | 4 8 | 2 6 | 3 7 | 4 5 | 2 6 | 1 7 | 1 8 | 20       | 3 5 | 2 4 | 6 8 | 3 7 | 4 5 | 2 6 | 1 7 | 1 8 | 21       | 3 5 | 2 4 | 3 6 | 7 8 | 4 5 | 2 6 | 1 7 | 1 8 | 22       | 3 5 | 2 4 | 3 6 | 4 7 | 5 8 | 2 6 | 1 7 | 1 8 | 23       | 3 5 | 2 4 | 3 6 | 4 7 | 2 5 | 6 8 | 1 7 | 1 8 | 24       | 3 5 | 2 4 | 3 6 | 4 7 | 2 5 | 1 6 | 7 8 | 1 8 | 25       | 3 5 | 2 4 | 3 6 | 4 7 | 2 5 | 1 6 | 1 7 | 8 8 | 26       | 3 5 | 2 4 | 3 6 | 2 4 | 5 7 | 1 6 | 1 7 | 8 8 | 27       | 3 5 | 2 4 | 3 6 | 2 4 | 1 5 | 6 7 | 1 7 | 8 8 | 28       | 3 5 | 2 4 | 3 6 | 2 4 | 1 5 | 1 6 | 7 7 | 8 8 | 29       | 3 5 | 2 4 | 2 3 | 4 6 | 1 5 | 1 6 | 7 7 | 8 8 | 30       | 3 5 | 2 4 | 2 3 | 1 4 | 5 6 | 1 6 | 7 7 | 8 8 | 31       | 3 5 | 2 4 | 2 3 | 1 4 | 1 5 | 6 6 | 7 7 | 8 8 | 32       | 2 3 | 4 5 | 2 3 | 1 4 | 1 5 | 6 6 | 7 7 | 8 8 | 33       | 2 3 | 2 4 | 3 5 | 1 4 | 1 5 | 6 6 | 7 7 | 8 8 | 34       | 2 3 | 2 4 | 1 3 | 4 5 | 1 5 | 6 6 | 7 7 | 8 8 | 35       | 2 3 | 2 4 | 1 3 | 1 4 | 5 5 | 6 6 | 7 7 | 8 8 | 36       | 2 3 | 1 2 | 3 4 | 1 4 | 5 5 | 6 6 | 7 7 | 8 8 | 37       | 2 3 | 1 2 | 1 3 | 4 4 | 5 5 | 6 6 | 7 7 | 8 8 | 38       | 1 2 | 2 3 | 1 3 | 4 4 | 5 5 | 6 6 | 7 7 | 8 8 | 39       | 1 2 | 1 2 | 3 3 | 4 4 | 5 5 | 6 6 | 7 7 | 8 8 | 40       | 1 1 | 2 2 | 3 3 | 4 4 | 5 5 | 6 6 | 7 7 | 8 8 | \sourceoff -- Valentin


   Profil
saphir
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.03.2005
Mitteilungen: 124
Wohnort: Baden-Württemberg
  Beitrag No.32, eingetragen 2008-08-17

Hallo allerseits, ich habe mir gestern die beiden Lösungen für n = 7 und n = 8 angesehen und daraus einen Algorithmus entwickelt, der mir die obere Schranke \ a_n <= 2/3 n^2 + n liefert. (Der lineare Term ist allerdings relativ grob abgeschätzt und könnte noch verbessert werden.) Da die untere Schranke von der Form \ a_n >= n(2n - 1)/3 ist, ergibt das zusammen die Asymptotik \ a_n = 2/3 n^2 + O(n). Für spezielle Werte erhalte ich etwas bessere Ergebnisse. \ n = 9: a_n <= 51 n = 10: a_n <= 65 n = 11: a_n <= 78 n = 12: a_n <= 95 Der Algorithmus ist einfach, aber ich habe gerade keine Ahnung, wie ich es so aufschreiben kann, dass man es nachvollziehen kann. Ich überlege es mir mal die nächsten Tage. Grüße, Saphir


   Profil
saphir
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.03.2005
Mitteilungen: 124
Wohnort: Baden-Württemberg
  Beitrag No.33, eingetragen 2008-08-17

Hallo, ich habe vorher bemerkt, dass 51 die optimale Anzahl für n = 9 sein sollte. Deswegen gebe ich mal meine Lösung dafür an: 0     99|88|77|66|55|44|33|22|11 1     99|88|77|56|56|44|33|22|11 2     99|88|77|56|45|46|33|22|11 3     99|88|57|67|45|46|33|22|11 4     99|88|57|46|57|46|33|22|11 5     99|88|57|46|45|67|33|22|11 6     99|88|57|46|45|36|37|22|11 7     99|58|78|46|45|36|37|22|11 8     99|58|47|68|45|36|37|22|11 9     99|58|47|46|58|36|37|22|11 10   99|58|47|46|35|68|37|22|11 11   99|58|47|46|35|36|78|22|11 12   99|58|47|46|35|36|27|28|11 13   59|89|47|46|35|36|27|28|11 14   59|48|79|46|35|36|27|28|11 15   59|48|47|69|35|36|27|28|11 16   59|48|47|36|59|36|27|28|11 17   59|48|47|36|35|69|27|28|11 18   59|48|47|36|35|26|79|28|11 19   59|48|47|36|35|26|27|89|11 20   59|48|47|36|35|26|27|18|19 21   45|89|47|36|35|26|27|18|19 22   45|48|79|36|35|26|27|18|19 23   45|48|37|69|35|26|27|18|19 24   45|48|37|36|59|26|27|18|19 25   45|48|37|36|25|69|27|18|19 26   45|48|37|36|25|26|79|18|19 27   45|48|37|36|25|26|17|89|19 28   45|48|37|36|25|26|17|18|99 29   45|34|78|36|25|26|17|18|99 30   45|34|37|68|25|26|17|18|99 31   45|34|37|26|58|26|17|18|99 32   45|34|37|26|25|68|17|18|99 33   45|34|37|26|25|16|78|18|99 34   45|34|37|26|25|16|17|88|99 35   45|34|23|67|25|16|17|88|99 36   45|34|23|26|57|16|17|88|99 37   45|34|23|26|15|67|17|88|99 38   45|34|23|26|15|16|77|88|99 39   45|34|23|12|56|16|77|88|99 40   45|34|23|12|15|66|77|88|99 41   34|45|23|12|15|66|77|88|99 42   34|24|35|12|15|66|77|88|99 43   34|24|13|25|15|66|77|88|99 44   34|24|13|12|55|66|77|88|99 45   34|12|34|12|55|66|77|88|99 46   34|12|13|24|55|66|77|88|99 47   13|42|13|24|55|66|77|88|99 48   13|12|34|24|55|66|77|88|99 49   13|12|23|44|55|66|77|88|99 50   11|23|23|44|55|66|77|88|99 51   11|22|33|44|55|66|77|88|99 Daran kann man auch gut erkennen, wie der oben erwähnete Algorithmus im Allgemeinen funktioniert. Zumindest bis Zeile 40, danach muss ich von der obigen Lösung abweichen, uns zwar so: 40   45|34|23|12|15|66|77|88|99 41   44|35|23|12|15|66|77|88|99 42   44|33|25|12|15|66|77|88|99 43   44|33|22|15|15|66|77|88|99 44   44|33|22|11|55|66|77|88|99 Warum das? Ich habe nun zwar "schlechtere" Umfomungen als oben durchgeführt, aber diese kann ich abschätzen, wenn ich a(4) kenne. Also \ a_9 <= 40 + 4 + a_4 und allgemeiner bekommt man \ a_(2n+1) <= 2n^2 + 3n + a_(n) a_(2n) <= 2n^2 + a_n (Der Fall n gerade ist einfacher...) Man muss sich natürlich genau überlegen, dass die obigen Umformungen immer zu dem gewünschten Egebnis führen. Das habe ich mir auch überlegt und es klappt, aber weiß nicht, wie ich es aufschreiben soll. Auf jeden Fall ergeben die beiden Rekursionsformeln mit einer Induktion z.B. die obere Schranke, die ich vorher angegeben habe. Gruß, Saphir


   Profil
Janik
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 09.01.2006
Mitteilungen: 274
Wohnort: Aachen, NRW
  Beitrag No.34, eingetragen 2008-08-18

Hallo, Lösungen für f(8) = 40 und f(9) = 51 wurden ja schon gepostet, das waren auch die optimalen Ergebnisse meiner Überlegungen. Zwischendurch hatte ich auch die Idee, eine Situation mit der Summe der Abstände der Kugeln vom Zielpunkt zu bewerten. Daraus entwickelte sich eine Idee, wie man die verschiedenen möglichen Züge bewerten kann: Selbstverständlich tausche ich immer eine größere Kugel (links) mit einer kleineren (rechts). Wenn ich mir eine der n-1 Tauschmöglichkeiten angucke, kommt ebenso selbstverständlich nur die größere Kugel im linken Tauschfach und die kleinere Kugel im rechten Tauschfach in Frage. Jetzt bewerte ich die "Effizienz" dieses Zuges mit der Differenz dieser beiden Kugeln und führe den Zug aus, bei dem die beiden vertauschten Kugeln den größtmöglichen Abstand haben. Ich vermute, dass diese Bewertung etwas feiner ist als die Variante, nur die Positionen der Kugeln zu bewerten. Problem: Häufig gibt es mehr als eine Tauschmöglichkeit mit der optimalen Verbesserung. Wenn ich an diesen Stellen immer einfach irgendeine auswähle, bekomme ich mitunter nicht die idealen Lösungen. Deswegen habe ich meinen Algorithmus alle Möglichkeiten mit optimaler Verbesserung ausprobieren lassen und komme auf die oben genannten Werte. Dummerweise konnte ich die Überlegungen noch nicht analytisch verwenden und mir auch noch keinen sinnvollen Algorithmus ausdenken, nach dem ich unter verschiedenen optimalen Verbesserungen die "beste" auswähle. Gruß


   Profil
zudumm
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 27.09.2004
Mitteilungen: 10
Wohnort: Schweiz/Tuerkei
  Beitrag No.35, eingetragen 2008-08-20

Hallo Valentin Danke fürs Auflisten der optimalen Lösung für n 7 und 8.. Ich wäre total dankbar , wenn du auch 3, 4, 5 und 6 auflisten könntest.. Ich hoffe, du findest etwas Zeit dazu und es müssten nicht alle n aufeinmal sein.. N = 3 würde auch schon sehr helfen.. Danke im Voraus, Grüsse an alle; Zudumm


   Profil
valentin
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.03.2005
Mitteilungen: 1478
Wohnort: Berlin
  Beitrag No.36, eingetragen 2008-08-21

Hallo Zudumm und Willkommen! Eine Lösung für N=3 in 5 Zügen sollte man ja eigentlich selber finden können. Aber gut: \sourceon 0        | 3 3 | 2 2 | 1 1 | 1        | 2 3 | 2 3 | 1 1 | 2        | 2 3 | 1 2 | 1 3 | 3        | 1 2 | 2 3 | 1 3 | 4        | 1 2 | 1 2 | 3 3 | 5        | 1 1 | 2 2 | 3 3 | \sourceoff N=4 \sourceon 0        | 4 4 | 3 3 | 2 2 | 1 1 | 1        | 4 4 | 2 3 | 2 3 | 1 1 | 2        | 2 4 | 3 4 | 2 3 | 1 1 | 3        | 2 4 | 2 3 | 3 4 | 1 1 | 4        | 2 4 | 2 3 | 1 3 | 1 4 | 5        | 2 2 | 3 4 | 1 3 | 1 4 | 6        | 2 2 | 1 3 | 3 4 | 1 4 | 7        | 2 2 | 1 3 | 1 3 | 4 4 | 8        | 2 2 | 1 1 | 3 3 | 4 4 | 9        | 1 2 | 1 2 | 3 3 | 4 4 | 10       | 1 1 | 2 2 | 3 3 | 4 4 | \sourceoff N=5 \sourceon 0        | 5 5 | 4 4 | 3 3 | 2 2 | 1 1 | 1        | 5 5 | 3 4 | 3 4 | 2 2 | 1 1 | 2        | 5 5 | 3 4 | 2 3 | 2 4 | 1 1 | 3        | 3 5 | 4 5 | 2 3 | 2 4 | 1 1 | 4        | 3 5 | 2 4 | 3 5 | 2 4 | 1 1 | 5        | 3 5 | 2 4 | 2 3 | 4 5 | 1 1 | 6        | 3 5 | 2 4 | 2 3 | 1 4 | 1 5 | 7        | 2 3 | 4 5 | 2 3 | 1 4 | 1 5 | 8        | 2 3 | 2 4 | 3 5 | 1 4 | 1 5 | 9        | 2 3 | 2 4 | 1 3 | 4 5 | 1 5 | 10       | 2 3 | 2 4 | 1 3 | 1 4 | 5 5 | 11       | 2 3 | 1 2 | 3 4 | 1 4 | 5 5 | 12       | 2 3 | 1 2 | 1 3 | 4 4 | 5 5 | 13       | 1 2 | 2 3 | 1 3 | 4 4 | 5 5 | 14       | 1 2 | 1 2 | 3 3 | 4 4 | 5 5 | 15       | 1 1 | 2 2 | 3 3 | 4 4 | 5 5 | \sourceoff N=6, dies ist die einzige Anomalie bis einschliesslich N=9! \sourceon 0        | 6 6 | 5 5 | 4 4 | 3 3 | 2 2 | 1 1 | 1        | 6 6 | 4 5 | 4 5 | 3 3 | 2 2 | 1 1 | 2        | 6 6 | 4 5 | 3 4 | 3 5 | 2 2 | 1 1 | 3        | 6 6 | 4 5 | 3 4 | 2 3 | 2 5 | 1 1 | 4        | 4 6 | 5 6 | 3 4 | 2 3 | 2 5 | 1 1 | 5        | 4 6 | 3 5 | 4 6 | 2 3 | 2 5 | 1 1 | 6        | 4 6 | 3 5 | 2 4 | 3 6 | 2 5 | 1 1 | 7        | 4 6 | 3 5 | 2 4 | 2 3 | 5 6 | 1 1 | 8        | 4 6 | 3 5 | 2 4 | 2 3 | 1 5 | 1 6 | 9        | 4 6 | 2 3 | 4 5 | 2 3 | 1 5 | 1 6 | 10       | 4 6 | 2 3 | 2 4 | 3 5 | 1 5 | 1 6 | 11       | 2 4 | 3 6 | 2 4 | 3 5 | 1 5 | 1 6 | 12       | 2 4 | 2 3 | 4 6 | 3 5 | 1 5 | 1 6 | 13       | 2 4 | 2 3 | 3 4 | 5 6 | 1 5 | 1 6 | 14       | 2 4 | 2 3 | 3 4 | 1 5 | 5 6 | 1 6 | 15       | 2 4 | 2 3 | 3 4 | 1 5 | 1 5 | 6 6 | 16       | 2 4 | 2 3 | 3 4 | 1 1 | 5 5 | 6 6 | 17       | 2 4 | 2 3 | 1 3 | 1 4 | 5 5 | 6 6 | 18       | 2 2 | 3 4 | 1 3 | 1 4 | 5 5 | 6 6 | 19       | 2 2 | 1 3 | 3 4 | 1 4 | 5 5 | 6 6 | 20       | 2 2 | 1 3 | 1 3 | 4 4 | 5 5 | 6 6 | 21       | 2 2 | 1 1 | 3 3 | 4 4 | 5 5 | 6 6 | 22       | 1 2 | 1 2 | 3 3 | 4 4 | 5 5 | 6 6 | 23       | 1 1 | 2 2 | 3 3 | 4 4 | 5 5 | 6 6 | \sourceoff N=7 und N=8 habe ich ja schon gepostet, und die Lösung für N=9 von Saphir sollte auch optimal sein, da sie mit der unteren Schranke zusammenfällt. Wer immer beim Betrachten dieser Ausgaben die entscheidende Idee zur Problemlösung hat und die 1000 Euro absahnt, der schuldet mir ein Bier! -- Valentin


   Profil
KnutKnutsson
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 11.08.2008
Mitteilungen: 26
  Beitrag No.37, eingetragen 2008-08-21

Oh Mann, ich betrachte die Lösungen schon seit einiger Zeit, ohne da was zu sehen. Wird wohl nix mit dem Bier, Valentin^^ Da die Lösungen ja alles andere als eindeutig sind, versuch ich sie gerade in ähnliche Form zu trimmen. Die Reihenfolge einiger Vertauschungen ist ja egal. Ich versuch sozusagen herauszufinden, dass der vierte Tausch zwischen Schublade 3 und 4 frühestens nach dem ersten Tausch zwischen Schublade 1 und 2 kommen darf, spätestens aber nach dem siebten kommen muss (nur als Illustration, vielleicht bringt das ja jemanden noch auf eine Idee). Interessant ist beim Algorithmus von Saphir, dass er ab n=10 auch über der unteren Schranke liegt, für n=8 liefert er 42 und ist also auch nicht optimal. Funktioniert wohl nur für n=9. Bei n=17 liegt aber sogar nur eins drüber, also auch nicht schlecht. Ich hatte ja schon mal den Verdacht geäußert, dass die untere Schranke vielleicht bis auf "wenige" Ausnahmen scharf sein könnte. Ich hab mir die Aufgabe auch mal ein bisschen verallgemeinert. Bei k Kugeln in n Schubladen scheint ab einer gewissen Grenze der Aufwand exakt linear in k zu wachsen. Da kann man eine nette Struktur aufbauen, mit der man recht schnell n Kugeln in der Reihenfolge umdrehen kann.  Bei 10 Schubladen braucht man zum Beispiel nur 25 Züge mehr, um eine weitere Kugel pro Schublade tauschen zu können. Naja, bloß hat mir das auch noch nicht weitergeholfen^^ Viele Grüße Knut


   Profil
Buri
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2003
Mitteilungen: 46686
Wohnort: Dresden
  Beitrag No.38, eingetragen 2008-08-21

Hi, ich habe ein wenig über das Rätsel nachgedacht, aber noch nicht allzuviel gerechnet, ich habe nur spaßeshalber eine Lösung für n = 150 mit ca. 17000 Zügen ermittelt, aber das ist furchtbar schlecht, obwohl es deutlich unter n2 - n liegt. Die Stellungen können gruppentheoretisch interpretiert werden, ebenso wie es beim Rubikschen Zauberwürfel auch auf natürliche Weise möglich ist. In der symmetrischen Gruppe S = S2n gibt es die von (12), (34), ..., (2n-1 2n) erzeugte Untergruppe H mit 2n Elementen. Die Menge aller Doppelnebenklassen, also der Teilmengen von S der Form H * g * H, ist die Menge der Stellungen in diesem Spiel. Leider sind Doppelnebenklassen, anders als linke und rechte Nebenklassen, nicht immer gleichmächtig. Wenn eine Stellung k "Doppelfächer" hat (die Nummern in einem Fach sind gleich), dann hat die Doppelnebenklasse, die dieser Stellung entspricht, 22n-k Elemente. Es gibt n - 1 Züge, jeder von ihnen führt von einer Doppelnebenklasse (Stellung) zu maximal vier anderen. Jede Lösung des Rätsels kann man "umdrehen", also von hinten nach vorne mit umgedrehten Kugelnummern (oder Krawatten-Nummern? wink ) lesen. Es könnte auch symmetrische Lösungen geben, das heißt solche, die beim Umdrehen unverändert bleiben. Keineswegs ist sicher, daß es eine symmetrische Optimallösung gibt, aber wenn man nur symmetrische Lösungen sucht, könnte man eine erschöpfende Suche, die wohl bis n = 9 noch einigermaßen machbar ist, auf ungefähr die doppelte "Krawattenanzahl" ausdehnen. Ich weiß, die Bezeichnung Krawatten (ties) ist ein Übersetzungsfehler. Gruß Buri


   Profil
checkit
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 06.06.2007
Mitteilungen: 642
Wohnort: Marburg, Hessen
  Beitrag No.39, eingetragen 2008-08-21

Hallo! Ich habe einen simplen Algorithmus entwickelt, der für n=150 16255 Züge braucht. Für n=8 allerdings 45 Züge, also deutlich über dem Minimum.  Was ich mich frage ist, ob es einen Algorithmus gibt, der für alle n die minimale Anzahl von Zügen braucht. Es könnte ja auch zwei verschiedene Algorithmen geben, von denen der eine für bestimmte n besser ist, als der andere und der andere wiederum für andere n besser ist als der erste. Ich würde auch gerne wissen was so die anderen für n=150 rausbekommen. Vermutlich ist 16255 grottenschlecht. Gruss checkit


   Profil
-->> Fortsetzung auf der nächsten Seite -->>
Seite 1Gehe zur Seite: 1 | 2 | 3 | 4 | 5  

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