Es gebe n Mengen v(i) mit jeweils k Elementen. Zwei dieser Mengen v(i) und v(j) haben sofern j ungleich i genau ein Element gemeinsam. Ein Beispiel wäre: k=2, n=3, v(0)={0,1}, v(1)={1,2}, v(2)={2,0}. Wie ist der Zusammenhang zwischen k und n? Gibt es überhaupt zu jedem k eine passende Lösung? Kann man noch weiter verallgemeinern? x gemeinsame Elemente?
Diese Fragestellung ist nicht so trivial wie sie aussieht, ich rechne nicht damit dass ich hier eine komplette Antwort auf alle Fragen bekomme. Aber ich kann mir nicht vorstellen, dass sich bisher keiner damit auseinandergesetzt hat. Es gab doch so viele Mathematiker die ganz andere Sachen beweisen können. Oder ist denen das zu trivial gewesen? Kennt jemand eine Internetseite oder ein Buch, wo Lösungsansätze dazu zu finden sind? Hat das Problem vielleicht einen Namen?
2009-07-23T07:53:49Z
eine frage hab ich noch vergessen: gibt es eine allgemeine vorschrift um v(i) zu bilden wenn k und n bekannt sind? (im Beispiel v(i) = {i, i+1 mod 3})
2009-07-24T10:37:09Z
gegenbeispiel: k=3, n=7. (k<n-1) v(i)={i, i+1 mod 7, i+3 mod 7}.
man muss jetzt nicht mal alle kombinationen durchgehen, es genügt für v(0) zu überprüfen dass sie mit allen anderen mengen genau ein element gemeinsam hat. das ist offensichtlich so. aufgrund der bildungsvorschrift kann man das auf alle anderen i übertragen. für k=4 ist übrigens n=13 und v(i)={i,i+1,i+3,i+9}. jeweils modulo 13. es gibt noch andere bildungsvorschriften, z.b. für k=3, n=7, v(i)={i,i+1,i+5}.
aber danke für deine antwort. habe nicht alles verstanden, aber kann gut sein dass meine formulierung missverständlich war.
ein paar details habe ich anscheinend auch vergessen zu erwähnen. die triviale lösung (ein element in allen mengen) geht dann nicht mehr: es soll n mögliche elemente geben die auftreten können. und jedes dieser n elemente ist in k mengen enthalte
2009-07-24T10:37:33Z
zum hintergrund: das ist ein problem aus der informatik, es geht darum in einem verteilten system bei gleichmäßiger lastverteilung wechselseitigen ausschluss zu gewährleisten, dieses problem lässt sich auf das mengentheoretische problem oben reduzieren.
hsc5912009-07-24T07:54:17Z
Beste Antwort
Hallo, hier handelt es sich um ein Problem aus der Mengentheorie bzw. Kombinatorik, das aber eigentlich doch trivial ist um Deinen Wortlaut aufzugreifen (so drückt sich ein Mathematiker nämlich oft gerne aus, wenn etwas nicht offensichtlich ist, er es aber nach evtl. längerem Nachdenken verstanden hat und es dann eigentlich doch einfach ist. Egal zum Thema ...) Deine Aufgabenstellung kann man mengentheoretisch so formulieren: Gesucht sind n Mengen, deren paarweise Schnittmenge genau ein Element enthält. Sei K(A) das Komplement von A und A & B die Schnittmenge von A und B. Dann muss für die Mächtigkeiten aller o.B.d.A 1 <= i < j <= n Mengen unten gelten, dass sie genau ein Element enthalten. K(v(1)) & ... & K(v(i-1)) & v(i) & K(v(i+1)) & ... & K(v(j-1)) & v(j) & K(v(j+1)) & ... & K(v(n)) Wieviele dieser derartigen Mengen können gebildet werden? Wieoft kann man 2 von n Mengen nehmen und die Schnittmenge bilden? Dies sind die aus der Kombinatorik bekannten n über 2 oder eben n*(n-1)/2. (Bemerkung: Diesselbe beliebte Frage aus der Kombinatorik ist, auf wieviele verschiedene Arten können sich n Personen die Hände schütteln) Da für jede der n Mengen gilt, dass sie mit jeder der anderen n -1 Mengen und nur mit dieser genau ein Element gemeinsam hat, muss jeder der n Mengen mindestens n-1 Elemente enthalten. Es muss also k>=n-1 gelten. Die restlichen k - n +1 Elemente jeder der n Mengen sind frei wählbar. Sie müssen nur paarweise verschieden sein und verschieden zu den n*(n-1)/2 der Schnittmengen. Insgesamt braucht man damit: n*(n-1)/2 + n*(k-n+1) verschiedene Elemente, um derartige n Mengen mit jeweils k Elementen bilden zu können. Zu Deinen Fragen: Wie ist der Zusammenhang zwischen k und n? k>=n-1 Gibt es überhaupt zu jedem k eine passende Lösung? Für alle k < n-1 gibt es keine Lösung. Kann man noch weiter verallgemeinern? x gemeinsame Elemente? Ja. Entsprechend muss gelten k>=x*(n-1), da ja jede der obigen Schnittmengen dann x Elemente enthält.
Eine Abbildungsvorschrift: v(i,j) sei das j-te Element der Menge v(i). 0 <= i <= n - 1, 0 <= j <= k - 1
v(i,j) ist in 3 Zweigen definiert: i = n - 1: j * (k+1) j < i < n -1: j * k + i sonst: i * k + j
Abbildungsvorschriften gibt es aber unendlich viele. Interessanter wäre es eine solche zu finden, die mit den Zahlen aus {0, .., n*(n-1)/2 + n*(k-n+1)-1} auskommt und zudem möglichst wenig Definitionszweige enthält.
Interessant ist es zu dem, die Fragestellung so zu erweitern, dass x dieser Mengen genau y Elemente gemeinsam haben. Die gebe ich Dir jetzt aber als Übung *gg*.
lg
Mit Deinen beiden Einschränkungen:
1) es soll n mögliche elemente geben die auftreten können. 2) und jedes dieser n elemente ist in k mengen enthalten
schaut die Aufgabenformulierung natürlich ganz anders aus. Damit sind meine Ausführungen hinfällig, da ja die Elemente der Schnittmengen nicht mehr paarweise verschieden sein dürfen, da sonst die Anzahl der n möglichen Elemente überschritten wird. Die Aussage k>= n-1 bezog sich entsprechend auf die von mir konstruierten Mengen. Die Grösse k kam mir in Deiner ursprünglichen Aufgabenstellung gleich etwas komisch bzw. willkürlich vor. Aber mit diesen beiden Einschränkungen macht es natürlich mehr Sinn. Ich recherchiere mal ein bisschen und melde mich, wenn ich was finde.
Leider hat meine Recherche nichts direkt passendes ergeben, so dass ich mir dazu ein paar eigene Gedanken gemacht habe. Leider ist meine Zeit wegen Familie und Arbeit (übrigens auch IT) sehr beschränkt, so dass ich nichts Durchgehendes vorzuweisen habe.
Eine hinreichende Bedingung ist: k * (k-1) = n -1. In diesen Fällen lassen sich jeweils n Mengen mit den obigen Bedingungen konstruieren. Ein solches Verfahren wäre auch leicht EDV-technisch umzusetzen. Es ist aber momentan mehr eine Heuristik, da ich einen durchgängigen Beweis (noch) nicht geschafft habe. Ich habe das Verfahren bis n=21 und k=5 ausprobiert. Dieses Verfahren liefert dann auch gleich mehrere Zerlegungen.
Ob diese Bedingung allerdings notwendig ist, weiss ich nicht und habe mir keinerlei Gedanken über die Gegenrichtung gemacht. D.h. also gibt es nicht doch auch n und k mit n-1 <> k(k-1), für die es auch n Mengen mit den obigen Bedingungen gibt.
Jedenfalls ein sehr interessantes Problem. Tut mir leid, aber mehr kann ich Dir nicht helfen. Ich muss mich (leider) wieder um meine eigenen Probleme kümmern. lg
Ich hab mir das ja heute im Mainzer Dom angeschaut und kann additionally für eine etwas getragene Unterstimmung sorgen. Das macht den gemeinsamen Gesang dann, wie soll ich sagen, tiefsinniger, fröhlich und tiefsinnig zugleich sozusagen. Aber andererseits, so ein ordentliches "Schuuuuh wap, schuh wap, schuuuuh wap, schuh wap hat ja auch became...