Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Kombinatorik & Graphentheorie » Zweiergruppen
Autor
Universität/Hochschule Zweiergruppen
tom12345
Neu Letzter Besuch: im letzten Monat
Dabei seit: 23.06.2022
Mitteilungen: 4
  Themenstart: 2022-06-27

Hallo, ich habe ein Problem, welches vermutlich sehr schwierig zu lösen ist. Es geht darum: Ich will Zweiergruppen bilden aus einer gerade Anzahl von Personen. Man kann sich das für folgendes Problem vorstellen: An einem Turnier soll jede Person gegen jede andere Person spielen (aber nur einmal, also AB ist gleich BA). Es gibt verschiedene Spieltage und jede Person soll an jedem Tag genau einmal spielen. Die Möglichkeiten, die es gibt sind leicht zu berechnen und wurden auch schon in einem anderen Thread ausführlich diskutiert. Ich soll mein Problem aber nochmal neu posten. Anzahl an Möglichkeiten bei z.B. n=10 Personen: \[\binom{10}{2}\cdot\binom{8}{2}\cdot\binom{6}{2}\cdot\binom{4}{2}\cdot\binom{2}{2}\] So weit, so gut. Ich bin aber nicht nur daran interessiert, wie viele Lösungen/Möglichkeiten es gibt, sondern an den Lösungen selbst. Eine einzige Lösung würde mir schon reichen. Ich habe das Problem bereits rekursiv (Tiefensuche) gelöst, jedoch scheint es so zu sein, dass es praktisch unlösbar ist, wenn n zu groß wird. Bei mir geht es bis n=8 ohne Probleme, bei n=10 dauert es schon seeeehr lange. An n=30, was mein Ziel wäre, denke ich noch gar nicht. Hat dazu jemand eine Idee? Oder kann jemand bestätigen, dass das Problem diese Schwierigkeit hat für große n? Danke und viele Grüße!


   Profil
Vercassivelaunos
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 28.02.2019
Mitteilungen: 1267
  Beitrag No.1, eingetragen 2022-06-27

\(\begingroup\)\(\newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\F}{\mathbb{F}} \newcommand{\K}{\mathbb{K}} \newcommand{\E}{\mathbb{E}} \newcommand{\H}{\mathbb{H}} \newcommand{\D}{\mathrm{D}} \newcommand{\d}{\mathrm{d}} \newcommand{\i}{\mathrm{i}} \newcommand{\e}{\mathrm{e}} \newcommand{\diag}{\operatorname{diag}} \newcommand{\span}{\operatorname{span}} \newcommand{\im}{\operatorname{im}} \newcommand{\id}{\operatorname{id}} \newcommand{\grad}{\operatorname{grad}} \newcommand{\zyk}[1]{\Z/#1\Z} \newcommand{\matrix}[1]{\left(\begin{matrix}#1\end{matrix}\right)} \newcommand{\vector}[1]{\left(\begin{array}{c}#1\end{array}\right)} \newcommand{\align}[1]{\begin{align*}#1\end{align*}} \newcommand{\ket}[1]{\left\vert#1\right>} \newcommand{\bra}[1]{\left<#1\right\vert} \newcommand{\braket}[2]{\left<#1\middle\vert#2\right>} \newcommand{\braketop}[3]{\left<#1\middle\vert#2\middle\vert#3\right>} \newcommand{\mean}[1]{\left<#1\right>} \newcommand{\lvert}{\left\vert} \newcommand{\rvert}{\right\vert} \newcommand{\lVert}{\left\Vert} \newcommand{\rVert}{\right\Vert} \newcommand{\Abb}{\operatorname{Abb}}\) Hallo Tom12345, die Anzahl an Möglichkeiten wächst tatsächlich sehr schnell. Für $n$ Personen ($n$ gerade) gibt es ja folgende Anzahl Möglichkeiten: $${n\choose 2} {n-2\choose 2}\dots{2\choose 2}=\frac{n(n-1)}{2}\frac{(n-2)(n-3)}{2}\dots\frac{2\cdot1}{2}=\frac{n!}{2^{\frac n2}}\\ $$ Da die Fakultät deutlich schneller wächst als die Exponentialfunktion, haut dir das sehr schnell für $n\to\infty$ ab. Viele Grüße Vercassivelaunos\(\endgroup\)


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 7855
Wohnort: Milchstraße
  Beitrag No.2, eingetragen 2022-06-27

\quoteon(2022-06-27 12:19 - tom12345 im Themenstart) ich habe ein Problem, welches vermutlich sehr schwierig zu lösen ist. \quoteoff Nö 🙃 Bei der Fußballbundesliga gibt es bspw. n = 18 Vereine. Und die können jeder gegen jeden an 17 Spieltagen spielen. Bei beliebigem geraden n braucht man sicherlich mindestens n-1 Spieltage. Aber damit kommt man auch aus! Du kannst nämlich wie folgt einen Spielplan basteln. Wenn ich es richtig verstanden habe, ist das dein eigentliches Ansinnen. Die Spieler mögen aus der Menge {0, 1, ..., n-1} bestehen. Es gibt die Spieltage 0, 1, ..., n-2. Am Spieltag Nr. j (\(j\in\{0,1,...,n-2\}\)) spielt Spieler j gegen Spieler n-1. Außerdem spielt Spieler a gegen Spieler b genau dann, wenn \(a+b\equiv 2j\mod n-1\), (\(a,b\in\{0,1,...,n-2\}\setminus\{j\}\)). Beispiel für n = 30: Am Spieltag Nr. 11 kommt es zu folgenden 15 Begegnungen \sourceon 11 - 29 10 - 12 9 - 13 8 - 14 7 - 15 6 - 16 5 - 17 4 - 18 3 - 19 2 - 20 1 - 21 0 - 22 28 - 23 27 - 24 26 - 25 \sourceoff Übrigens gestehe ich, dass ich das bei Wikipedia gespickt habe. (Beispiel zu: Ein vollständiger Graph $K_n$ mit n Knoten ist mit n - 1 Farben kantenfärbbar.)


   Profil
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6994
Wohnort: Niedersachsen
  Beitrag No.3, eingetragen 2022-06-28

Es gibt auch eine Lösung, die sich leicht organisieren lässt. Angenommen wir haben vier(*) Spielfelder / Tische o.ä. an denen die Zweikämpfe stattfinden. Wir ordnen sie so an: \sourceon 1. Runde Spieler 2 Spieler 3 Spieler 4 Spieler 8 Tisch A Spieler 1 Tisch B Tisch C Tisch D Spieler 7 Spieler 6 Spieler 5 \sourceoff Ein Spieler im Beispiel die Nummer 8 nimmt eine Sonderrolle ein. Er bleibt immer an seinem Platz. Die erste Runde ist oben abgebildet. Nach der ersten Runde Rücken die Spieler 1 bis 7 im Kreis je einen Platz weiter. Also 1->2->3->4->5->6->7->1. Die Anordnung sieht dann so aus: \sourceon 2. Runde Spieler 1 Spieler 2 Spieler 3 Spieler 8 Tisch A Spieler 7 Tisch B Tisch C Tisch D Spieler 6 Spieler 5 Spieler 4 \sourceoff Nach der zweiten Runde rücken 1 bis 7 wieder einen Platz weiter usf. Nach sieben Runden hat jeder gegen jeden gespielt. Bei einer ungeraden Anzahl von Spielern gibt es keinen Spieler 8. Wer am Tisch A sitzt, pausiert. (*) Das Verfahren funktioniert für jede Anzahl an Spielern. Acht Spieler, die vier Paare bilden ist nur ein Beispiel.


   Profil
tom12345
Neu Letzter Besuch: im letzten Monat
Dabei seit: 23.06.2022
Mitteilungen: 4
  Beitrag No.4, vom Themenstarter, eingetragen 2022-06-29

\quoteon(2022-06-28 19:43 - Kitaktus in Beitrag No. 3) Es gibt auch eine Lösung, die sich leicht organisieren lässt. Angenommen wir haben vier(*) Spielfelder / Tische o.ä. an denen die Zweikämpfe stattfinden. Wir ordnen sie so an: \sourceon 1. Runde Spieler 2 Spieler 3 Spieler 4 Spieler 8 Tisch A Spieler 1 Tisch B Tisch C Tisch D Spieler 7 Spieler 6 Spieler 5 \sourceoff Ein Spieler im Beispiel die Nummer 8 nimmt eine Sonderrolle ein. Er bleibt immer an seinem Platz. Die erste Runde ist oben abgebildet. Nach der ersten Runde Rücken die Spieler 1 bis 7 im Kreis je einen Platz weiter. Also 1->2->3->4->5->6->7->1. Die Anordnung sieht dann so aus: \sourceon 2. Runde Spieler 1 Spieler 2 Spieler 3 Spieler 8 Tisch A Spieler 7 Tisch B Tisch C Tisch D Spieler 6 Spieler 5 Spieler 4 \sourceoff Nach der zweiten Runde rücken 1 bis 7 wieder einen Platz weiter usf. Nach sieben Runden hat jeder gegen jeden gespielt. Bei einer ungeraden Anzahl von Spielern gibt es keinen Spieler 8. Wer am Tisch A sitzt, pausiert. (*) Das Verfahren funktioniert für jede Anzahl an Spielern. Acht Spieler, die vier Paare bilden ist nur ein Beispiel. \quoteoff Super, vielen Dank! Das hilft mir weiter! 😃


   Profil
tom12345 hat die Antworten auf ihre/seine Frage gesehen.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]