Veständnisproblem einer seltsamen Konstruktion

Neue Frage »

schmouk Auf diesen Beitrag antworten »
Veständnisproblem einer seltsamen Konstruktion
Hallo die Herren,

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
Reksilat Auf diesen Beitrag antworten »
RE: Veständnisproblem eine seltsamen Konstruktion
Tach auch,

Zitat:
Hallo die Herren

Lass das bloß nicht tigerbine sehen. Big Laugh

Gibt es nicht noch irgendwelche Einschränkungen? Man kann doch schließlich

setzen, dann ist , da es ja Paare mit Abstand 7 gibt. verwirrt

Gruß,
Reksilat.
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...
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
verwirrt


Gruß,
Reksilat.
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... verwirrt
Reksilat Auf diesen Beitrag antworten »
RE: Veständnisproblem eine seltsamen Konstruktion
Ich dachte 6+7=11. verwirrt Taschenrechner sagt auch 13. Big Laugh
 
 
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
Reksilat Auf diesen Beitrag antworten »

Zitat:
Es geht so: gerade, wobei der oben definierte Mindestabstand ist. Dann existiert eine Teilmenge so, dass gilt für alle ungerade.

Das Problem ist trivial: . smile
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.

Zitat:
Nehme ich jetzt an, ein n-Tupel a mit einer ungeraden Anzahl an von Null verschiedenen Komponenten befinde sich in...

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.
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:
Zitat:
Zeige, falls es einen binären Code, mit gerade gibt, dann existiert ein Code in dem alle Codewörter ein gerades Gewicht haben.


Und so ist das meines Erachtens dann auch nicht mehr trivial. Ich hatte die Bedingung der Elemente nicht mit eingebaut.

Besten Gruß,

Schmo
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.
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?
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.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »