Kombinatorik, maximale Menge, "einfaches" Problem?

12.01.2013, 21:21	blubbel	Auf diesen Beitrag antworten »
Kombinatorik, maximale Menge, "einfaches" Problem? Hallo Ich habe ein kleines Problem, zu dem ich die Lösung schon kenne, aber sie weder sehr intuitiv sonderlich anschaulich, noch formal beweisen kann. Zu einem festen $\begin{eqnarray} n\in\mathbb N \end{eqnarray}$ seien unsere Tupel $\begin{eqnarray} v\in\mathbb F_2^n=\{0,1\}^n \end{eqnarray}$ . Zu zwei Tupeln definieren wir $\begin{eqnarray} v=(v_1,\ldots,v_n)\le w=(w_1,\ldots,w_n) ~\Leftrightarrow~ v_i\le w_i~\forall i=1,\ldots,n \end{eqnarray}$ . Nun ist die maximale Kardinalität einer Menge M von solchen Tupeln gefragt, für die gilt: $\begin{eqnarray} v,w\in M,~v\le w ~\Rightarrow~ v=w \end{eqnarray}$ . Das bedeutet: Kein Tupel darf in allen Komponenten, in denen ein anderer Tupel Einsen hat, auch überall Einsen haben. Der Tupel mit Nullen in allen Koordinaten wird ausgeschlossen. Die korrekte Formel lautet $\begin{eqnarray} n\choose\lceil\frac{n}{2}\rceil \end{eqnarray}$ . Da diese quasi nur in einem Nebensatz erwähnt wurde, gehe ich stark davon aus, dass es entweder einen einfachen, kurzen Beweis gibt, oder eine anschauliche intuitive Erklärung (oder etwas nicht gerade einfaches wurde als trivial abgestempelt...). Zur Illustration hier ein paar Beispiele für eine solche maximale Menge: n=2 (1,0) (0,1) n=3 (1,0,0) (0,1,0) (0,0,1) Spannend wird es erst ab n=4. (1,1,0,0) (1,0,1,0) (1,0,0,1) (0,0,1,1) (0,1,0,1) (0,1,1,0) Ich brauche also entweder einen Beweis, oder eine Art "intuitive Erklärung", falls sich ein etwaiger Beweis als zu technisch oder uninteressant ergeben sollte. Probiert habe ich schon Induktion, bei Fallunterscheidung nach geradem oder ungeradem n. Hier mal ein kleiner Ansatz für n=2k (also ein Beweis, der die Behauptung für den Übergang von geradem zu ungeradem n führt): Annahme: Es gelte die Formel für n=2k. Schritt zu 2k+1: Angenommen, es gäbe mehr als die behauptete Anzahl an Vektoren in einer gültigen Menge für n=2k+1. Nach Annahme kann es maximal $\begin{eqnarray} {2k \choose k} \end{eqnarray}$ Vektoren mit einer 0 in der ersten Koordinate geben (ansonsten wählt man diese Vektoren, streicht die erste Koordinate und erhält mehr Vektoren als angenommen). Wegen $\begin{eqnarray} {2k+1 \choose k+1}={2k \choose k}+{2k \choose k+1} \end{eqnarray}$ müsste man jetzt zeigen, dass es nicht mehr als $\begin{eqnarray} {2k \choose k+1} \end{eqnarray}$ Möglichkeiten für die Vektoren mit einer 1 in der ersten Koordinate gibt. Wegen $\begin{eqnarray} {2k \choose k+1}<{2k \choose k} \end{eqnarray}$ ist das aber nicht gerade trivial :/
12.01.2013, 22:12	Mystic	Auf diesen Beitrag antworten »
RE: Kombinatorik, maximale Menge, "einfaches" Problem? Naja, rein intuitiv ist mir das sonnenklar... Nimm z.B. n=7 und überleg dir, welche 7-Tupel du in deine Menge maximaler Größe aufnehmen sollst... a) Solche mit lauter Nullen (oder dual dazu mit lauter Einsen)? Sicher nicht, denn das würde die restliche 2^7-1 Elemente für die weitere Auswahl ausschließen.. b) Solche mit einer 1 (oder dual dazu mit einer 0)? Auch schlecht, denn ich könnte dann nicht mehr irgendeine der 6 Nullen zu Einsern machen, oder die 1 zu 0... Das würde also (2^6 -1)+(2^1-1) Elemente für die weitere Auswahl ausschließen... c) Solche mit zwei Einsen (oder dual dazu mit zwei Nullen)? Auch schlecht, denn ich könnte dann nicht mehr irgendeine der 5 Nullen zu Einsern machen, oder die zwei 1'en zu 0'en... Das würde also (2^5 -1)+(2^2-1) Elemente für die weitere Auswahl ausschließen... d) Am besten fahre ich mit drei oder vier Einsen (oder dual dazu mit vier bzw. drei Nullen)... Das würde nämlich "nur" (2^4-1)+(2^3-1) Elemente für die weitere Auswahl ausschließen... Es ist daher nur logisch, dass ich ausschließlich solche Elemente (aber nicht gemischt!) auswählen und diesen "Pot" bis zum letzten dann ausschöpfen werde... Damit kommt man aber genau auf deine Anzahl...
13.01.2013, 21:38	blubbel	Auf diesen Beitrag antworten »
Vielen Dank! Das macht so Sinn und ich kann leicht verallgemeinert werden

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »