Verschiedene Partitionen mit einer kleinen Bedingung

Neue Frage »

Ulli Bruells Auf diesen Beitrag antworten »
Verschiedene Partitionen mit einer kleinen Bedingung
Vermutlich ist meine Frage (die eines Laien) hier völlig fehl am Platz, ich stelle sie trotzdem.

Ich möchte eine Menge (Anzahl der Elemente ist teilbar durch 4) in Teilmengen von je 4 Elementen zerlegen, und das auf so viele unterschiedliche Weisen wie möglich mit der Einschränkung, dass zwei Elemente, die einmal zur selben Teilmenge gehörten, in keiner anderen Zerlegung erneut zur selben Teilmenge gehören.

Beispiel: Eine Menge mit 16 Elementen {a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p}
1. Zerlegung (beliebig)
{{a,b,c,d},{e,f,g,h},{i,j,k,l},{m,n,o,p}}
2. Zerlegung
{{a,e,i,m},{b,f,j,n},{c,g,k,o},{d,h,l,p}}

Schon eine dritte solche Zerlegung scheint (im Fall von 16) zu scheitern. Meine Frage: Wie mächtig muss die Gesamtmenge sein, damit 3, 4, 5 ... solcher Zerlegungen möglich sind? - Oder umgekehrt gefragt: Wie viele solcher Zerlegungen gibt es, wenn die Mächtigkeit der Gesamtmenge (4n) vorgegeben ist?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Ulli Bruells
Wie mächtig muss die Gesamtmenge sein, damit 3, 4, 5 ... solcher Zerlegungen möglich sind?

Die "Pünktchen" da kannst du dir sparen:

Nehmen wir beispielsweise mal , dann sind in derselben Teilmenge n-1 andere Zahlen. Diese Zahlen dürfen in keiner anderen Zerlegung wieder in derselben Menge mit sein, dass trifft auch auf die zweiten Zahlen zu usw.

Schon unter diesem Gesichtspunkt kann es höchstens Zerlegungen geben! Für ist das Anzahl 5, für sogar nur Anzahl 4.

EDIT: Ach was, Unsinn überhaupt zu betrachten: Die Elemente einer Menge der ersten Zerlegung müssen ja in der zweiten Zerlegung bereits auf verschiedene Mengen aufgeteilt werden, also macht eh nur Sinn, wenn man auch nur wenigstens zwei Zerlegungen haben will.

EDIT2: Für n=2 ist die Maximalanzahl 7 von Zerlegungen möglich - das kennt man von den Liga-Spielplänen.
Ulli Bruells Auf diesen Beitrag antworten »
Verschiedene Partitionen mit einer kleinen Bedingung
Besten Dank, HAL 9000!

Natürlich wird die Zahl der möglichen Zerlegungen durch die Bedingung, dass sich zwei Elemente in keinem Fall mehr als einmal in einer Teilmenge "begegnen" sollen, stark eingeschränkt.

Die von Dir aufgestellte Obergrenze (4n-1)/(n-1) leuchtet zunächst ein, beißt sich aber leider mit der Empirie. Zum Beispiel sind bei n=9 (also bei 36 Elementen) fünf solcher Zerlegungen relativ leicht zu finden, obwohl nur vier möglich sein sollen.

Mich würde es auch überraschen, wenn es für n≥5 eine konstante Obergrenze (4) gäbe. Nehme ich zum Beispiel n = 25, also hundert Elemente, dann sind nach vier Zerlegungen für jedes Element erst 12 andere Elemente als Teilgruppen-Partner "verbrannt". Müsste wohl mit dem Teufel zugehen, wenn sich - bei jeweils 87 noch freien Elementen - nicht noch eine weitere Zerlegung konstruieren ließe.
HAL 9000 Auf diesen Beitrag antworten »

Ja Entschuldigung, hab wohl nicht genau genug gelesen:

Ich bin von 4 Teilmengen zu je n Elementen ausgegangen, statt von n Teilmengen zu je 4 Elementen.

Also vergiss (so gut wie) alles, was ich geschrieben habe, auch diese Abschätzung.
Neue Frage »
Antworten »



Verwandte Themen

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