| |
| Autor |
 Zweiergruppen |
|
tom12345
Neu 
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 
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 
Dabei seit: 19.01.2013
Mitteilungen: 7849
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
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
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. |
|
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]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
