Bearbeiten von: [Änderungshistorie]
  Zeilenumbrüche automatisch mache ich selbst mit HTML    

Ich möchte eine Mail an , nachdem mein Vorschlag bearbeitet ist.
  Nachricht zur Änderung:

Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
[Link zurück zum Kommentar]

Vorschau:
Re: Spektrum-Krawattenrätsel
Hallo zusammen, ich habe gestern auch einen Beweis fuer die untere Schranke von n(2n-1)/3 gefunden, ich vermute einmal stark, dass der Beweis von Peter Winkler in seinem Buch der Gleiche ist (ich habe das Buch nicht), da ich eine gaengige Potentialfunktion verwende, wie sie oft zu Beweisen in der Informatik verwendet werden (wir hatten diese Pot.Funktion mal beim Radix-Heap glaub ich). Falls die Beweise nicht gleich sind, vielleicht kann man ja dann die beiden Beweise kombinieren um eine bessere untere Schranke zu erhalten. Hat jemand das Buch? Ich werde einmal meinen Beweis (nicht super formal spezifiziert, aber sollte dennoch korrekt sein) angeben und im Anschluss noch ein Paar Gedanken, die ich mir zu dem Raetsel gemacht habe: Beweis untere Schranke n(2n-1)/3: Eine Stellung S beschreibe ich hier mit einer nx2 Matrix, z.B.: S = (1,4,3,4;3,2,2,1) ist eine Situation fuer n = 4. Man betrachtet eine Potentialfunktion f, die die Links-Rechts-Inversionen einer momentanen Stellung zaehlt. Eine Links-Rechts-Inversion ist ein Zustand, wo ein Eintrag der Matrix S einen Wert w_1 hat und es einen Wert w_2 rechts von w_1 gibt, der kleiner ist als w_1, oder es gibt einen Wert w_2, der links von w_1 ist und größer ist. Man kann sagen, dass eine Links-Rechts-Inversion ein Tupel aus der Matrix S ist, so dass deren Links-Rechts-Reihenfolge bezueglich der Zielposition noch nicht stimmt. Bezueglich der blau-markierten 2 in der zweiten Zeile und der zweiten Spaltein S haetten wir 2 Links-Rechts-Inversionen: S = (1,4,3,4;\red\ 3 \black\ ,\blue\ 2 \black\ ,2,\red\ 1 \black\ ) Man kann nun nachrechnen, dass in der Ausgangssituation S_0 der Laenge n gilt: f(S_0) = (n-1)2n Man kann nun 2 Elemente aus benachbarten Spalten in der Matrix S vertauschen (wir nennen das eine Swap Operation). Klar ist, dass bzgl. einer Swap Operation eines Elements aus Spalte x und eines Elements aus Spalte x+1 auch nur die Anzahl der Inversionen aus diesen Spalten aendern kann. Ein Swap von: (...,4,3,...;...,4,3,...) -> (...,3,3,...;...,4,4,...) Verringert die Anzahl der Inversionen von 4 auf 1, also um 3. Es gilt sogar, dass maximal die Anzahl der Inversionen pro Swap Operation um 3 verringert werden kann. Man erhaelt mit dieser Beobachtung bereits eine erste untere Schranke: Zu Beginn haben wir (n-1)2n Inversionen. Pro Swap Operation verringere ich maximal die Anzahl der Inversionen um 3, daher brauche ich mindestens (n-1)2n/3 Swap Operationen. Wie kommt man nun auf die (2n-1)n/3: Hierzu beobachtet man 2 besondere Situationen im Spiel. Das ist einmal: Der letzte Swap: Beim letzten Swap werden 2 Elemente vertauscht, so, dass 2 Spalten, die vor der swap Operation 2 verschiedene Zahlen beinhalteten nach der Operation nur noch die gleichen Zahlen beinhalten, also z.B.: (2,3;3,2) -> (2,3;2,3) Man erkennt, dass in der letzten Swap Operation nur eine Inversion vorhanden ist, nach der Swap Operation ist das Potential 0. Demnach existiert immer eine Swap Operation, die das Potential nur um 1 verringert (maximal verringert es sich ja um 3). Swaps, die eine Spalte komplettieren: Wie beispielsweise in folgender Situation: (4,4;3,1) -> (3,4;1,4) erkennt man, dass beim Komplettieren einer Spalte eine Potential- verringerung um 2 moeglich ist. Insgesamt bedeutet das, dass im optimalen Fall: - 1 Mal eine Potentialverringerung um 1 - (n-2) Mal eine Potentialverringerung um 2 - k Mal eine Potentialverringerung um 3 passiert. Wir berechnen das minimale k: (n-1)2n = 1 * 1 + (n-2) * 2 + k * 3 2n^2-2n = 1 + 2n - 4 + 3k 2n^2-4n + 3 = 3k k = (2n^2 - 4n + 3) / 3 Demnach haben wir mindestens insgesamt: k + 1 + (n - 2) = (2n-1)n / 3 Swap Operationen. Die Frage, die sich stellt, ist doch also nun, warum es bei vielen N auch moeglich ist, eine Abfolge zu finden, dass wenn man diese Potentialfunktion betrachtet, genau diese potentialverrinernden Swap-Operationen ausfuehrbar sind, und vor allem, warum es bei einigen N nicht moeglich ist. Ich habe dazu einmal eine Abfolge fuer N = 6 analysiert und komme dabei zu einem Zustand, wo man nur eine Potentialverringerung um 2 anstelle der optimalen 3 finden kann. Die Frage ist also nun, wieso kann es keine Swap-Folge fuer N = 6 geben, dass eine Situation vermeidbar ist, dass nur eine Swap-Operation mit Potentialverringerung um 2 moeglich ist anstelle der optimalen 3. Um das zu untersuchen faende ich eine Liste hilfreich, in der man die theoretisch optimalen Anzahlen auflistet und das, was man per Brute-Force Suche gefunden hat. Dann koennte man diese N untersuchen, wo man Swap Operationen mit Verringerung kleiner 3 ausfuehren muss. Vielleicht sieht man dann, wieso dann wieso das noetig ist. Viele Grüße, Christian
 
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]