Veständnisproblem einer seltsamen Konstruktion |
18.06.2010, 16:56 | schmouk | Auf diesen Beitrag antworten » | ||||
Veständnisproblem einer seltsamen Konstruktion Angenommen ich habe eine Teilmenge C des in der für paarweise verschiedene x,y gilt, das sie sich in mindestens 6 komponenten unterscheiden. Dieser unterschied wird als "Abstand" bezeichnet. Also (0,...,0) und (0,...,0,1,0,...0) haben also den abstand 1. Was aber nicht passieren kann, denn der Mindestabstand ist halt 6. okay. Ausserdem sind elemente in dieser Teilmenge C. Jetzt ist definiert dann ist , klar, da ist gerade M, da jeder einzelne "Vektor" zu sich selbst den Abstand 0 hat. Dann ist auch klar, wegen dem Mindestabstand. Jetzt wird angegeben, man könne ableiten, dass auch also für alle ungeraden i größer 6 gilt. Und nur über alle gerade i größergleich 6 können man nichts sage, ausser dass sie trivialerweise sind. Also . Hat jemand von euch ne Ahnung wie man darauf kommen kann? Grüße, Schmo |
||||||
18.06.2010, 20:14 | Reksilat | Auf diesen Beitrag antworten » | ||||
RE: Veständnisproblem eine seltsamen Konstruktion Tach auch,
Lass das bloß nicht tigerbine sehen. Gibt es nicht noch irgendwelche Einschränkungen? Man kann doch schließlich setzen, dann ist , da es ja Paare mit Abstand 7 gibt. Gruß, Reksilat. |
||||||
19.06.2010, 10:21 | Mystic | Auf diesen Beitrag antworten » | ||||
RE: Veständnisproblem eine seltsamen Konstruktion Ich vermute mal stark, dass 1. die Elemente von C nicht nur einen Abstand von mindestens 6 aufweisen, sondern dass tatsächlich der Mindestabstand 6 beträgt... 2. C sogar ein Unterraum des Vektorraums über sein sollte, und nicht nur eine Teilmenge... Wenn meine Vermutung zutrifft, dann wäre der Titel des Threads gar nicht schlecht gewählt, denn dann läge hier tatsächlich ein großes - um nicht zu sagen riesiges - Verständnisproblem vor, andernfalls entschuldige ich mich in aller Form... |
||||||
19.06.2010, 16:00 | Reksilat | Auf diesen Beitrag antworten » | ||||
RE: Veständnisproblem eine seltsamen Konstruktion Das ist schon mal eine Idee, aber dann ist doch zum Beispiel auch das hier ein Gegenbeispiel: a=00000000000000 b=11111100000000 c=00000001111111 d=11111101111111 Gruß, Reksilat. |
||||||
19.06.2010, 17:55 | Mystic | Auf diesen Beitrag antworten » | ||||
RE: Veständnisproblem eine seltsamen Konstruktion Ich denke, statt der Distanzen 11 gehört 13, aber als Gegenbeispiel funktioniert es trotzdem...Damit gehen mir auch langsam die Ideen aus, wie man die Aufgabenstellung "reparieren" könnte... |
||||||
19.06.2010, 20:55 | Reksilat | Auf diesen Beitrag antworten » | ||||
RE: Veständnisproblem eine seltsamen Konstruktion Ich dachte 6+7=11. Taschenrechner sagt auch 13. |
||||||
Anzeige | ||||||
|
||||||
24.06.2010, 23:53 | schmouk | Auf diesen Beitrag antworten » | ||||
Ein Stückchen bin ich weiter gekommen, und zwar soll es weiterhin tatsächlich nur eine Teilmenge und nicht zwingend ein Unterraum sein. Desweiteren kann das Problem verallgemeinert werden. Es geht so: gerade, wobei der oben definierte Mindestabstand ist. Dann existiert eine Teilmenge so, dass gilt für alle ungerade. Das lässt sich zurückführen auf folgendes Problem: gerade, dann existiert eine Teilemenge so, dass für jedes gilt: Die Anzahl der von Null verschiedenen Komponenten ist stets gerade. Gut, letztere Behauptung ist intuitiv erstmal irgendwie klar. Ich kann ja nun z.B. ein konstruieren, indem ich den Null"vektor" und das n-Tupel in die Menge setze. Jetzt ergibt sich alles weitere: In sind jetzt auch alle n-Tupel die ihre 1er-Blöcke um mindestens verschoben haben, denn die halten gegenseitig immer den vorausgesetzten Mindestabstand ein. Nehme ich jetzt an, ein n-Tupel mit einer ungeraden Anzahl an von Null verschiedenen Komponenten befinde sich in , dann krieg ich keinen klaren Widerspruch zustande, auch wenn ich weiß, dass es irgendwie immer ein n-Tupel gibt, bei dem der 1er-Block so liegt, dass das zu jenem den Mindestabstand nicht einhält. Aber ich kriegs nicht formal hingeschieben, könnt Ihr mir da helfen? Grüße, Schmo |
||||||
25.06.2010, 11:10 | Reksilat | Auf diesen Beitrag antworten » | ||||
Das Problem ist trivial: . Auch jede Menge mit erfüllt die Behauptung. Außerdem ist die Aufgabe nun etwas völlig anderes als oben, denn dort setzt Du eine Menge voraus, hier willst Du dagegen erst die Existenz einer solchen Menge zeigen.
Wozu solltest Du das tun? Nach der obigen Problemstellung musst Du Dir die Menge erst selbst konstruieren - dann packe doch solche Elemente gar nicht erst rein. Es gibt ja auch keinen Grund dazu. __________ Sag doch bitte mal, woher nun das Problem kommt, ob es da einen Zusammenhang zu etwas größerem gibt. Oder versuchst Du einfach nur, ein nichttriviales Problem zu finden und es dann zu lösen? Gruß, Reksilat. |
||||||
25.06.2010, 19:31 | schmouk | Auf diesen Beitrag antworten » | ||||
Hi. Ja Du hast recht, klar, so defininiert es Trivial. Es geht Ursprünglich um Fehlerkorrigierende Codes. Das Problem entstammt dem Buch "Introduction to Coding Theory" J.H. van Lint in dem einiges seltsam ist. Aber ich starte noch einen Versuch, denn so kann es nicht gemeint sein. Eine Teilmenge mit Elementen, des mit dem Mindestabstand wird einfach als Code bezeichnet. Sei so eine Teilemenge existent und gesetzt als und gerade. Zeige, dass es dann eine Teilmenge gibt, die ebenfalls Elemente hat, den Mindestabstand hat, dazu aber gilt, dass jedes Element eine gerade Anzahl an von Null verschiedenen Komponenten hat. Als -Code bezeichnet man schlicht jede Teilmenge des die Elemente hat und eben diesen mindestabstand . Ist so nennt man den Code binär. Und mit Gewicht bezeichnet man die Anzahl der von Null verschiedenen Komponenten in einem "Codewort", wobei ein Codewort wiederum einfach ein n-Tupel in einer solchen Teilmenge ist. Zitat (übersetzt) aus dem Buch:
Und so ist das meines Erachtens dann auch nicht mehr trivial. Ich hatte die Bedingung der Elemente nicht mit eingebaut. Besten Gruß, Schmo |
||||||
26.06.2010, 20:31 | Reksilat | Auf diesen Beitrag antworten » | ||||
Prima, damit lässt sich arbeiten. Nun überleg Dir doch mal, wie man alle Codewörter mit ungeradem Gewicht in Codewörter mit geradem Gewicht umwandeln kann. Gibt es eine Methode, mit der man für alle mit ungeradem Gewicht gewährleisten kann? Gruß, Reksilat. |
||||||
28.06.2010, 12:16 | schmouk | Auf diesen Beitrag antworten » | ||||
Danke, danke. Ja verstehe jetzt. Ich glaub mehr oder weniger müsste es soetwas sein: Sei ein binärer -Code mit gerade. Dann existiert ein -Code , in dem alle Codewörter gerades Gewicht haben.\\ Es gilt Hilfsaussage: Seien mit , genau dann ist entweder jeweils gerade oder jeweils ungerade.\\ Zerlege in und . Addiere zu allen Codewörtern in und erhalte eine Teilmenge in der alle Codewörter ebenfalls gerade sind.\\Prüfe nach: (i) (ii) hat Mindestabstand (iii) Alle Codewörter in haben die Länge (klar) Zeige also: (ii) Die Abstände zweier Codewörter in bzw. bleiben erhalten, also auch der Mindestabstand. Sei und , dann gilt mit der Hilfsaussage oben, dass also mindestens . Es ist also mindestens . (i) Angenommen dann wäre . Widerspruch zum Mindestabstand, da . Damit folgt die Behauptung. Kann man doch so machen, oder? LG Schmo ps.: Was sagt die Glaskugel für Argentinien? |
||||||
28.06.2010, 12:36 | Reksilat | Auf diesen Beitrag antworten » | ||||
Jo, prima. So hab ich mir das ebenfalls vorgestellt. Ist auch sauber argumentiert. Glaskugel gibt sich bisher leicht umwölkt. Ich sehe eine zwei auf deutscher Seite, mehr noch nicht... Gruß, Reksilat. |
|