Forum:  Kombinatorik & Graphentheorie
Thema: Alle Paare bilden
Themen-Übersicht
apollonius
Neu
Dabei seit: 23.09.2019
Mitteilungen: 3
Aus:
Themenstart: 2019-09-23 08:58

Hallo,

ich überlege gerade an folgendem Problem:

In einer Gruppe von 22 Personen sollen lauter Paare gebildet werden; da gibt es natürlich 231 Möglichkeiten.

In der ersten Runde werden nun 11 dieser Paare gebildet.
In der zweiten Runde werden 11 weitere mögliche Paare gebildet, usw.

Die Frage: ist es möglich, dass man in 21 Runden alle möglichen Paarungen realisiert? (Dabei darf/soll natürlich keine Paarung mehrfach vorkommen.)
Meine Vermutung ist: ja, das geht. (wie man sich für weniger als 22 Personen durch Ausprobieren schnell klarmacht)
Ich kanns aber nicht beweisen.

Interessant wäre auch ein Algorithmus, der einem für jede Runde die entsprechenden Paarungen liefert, sodass sich das mit 21 Runden ausgeht.

Ich überlege auf jeden Fall weiter und poste wenn ich auf eine Lösung komme, bin aber sehr gespannt auf eure Ideen 😄

Liebe Grüße


Diophant
Senior
Dabei seit: 18.01.2019
Mitteilungen: 4279
Aus: Rosenfeld, BW
Beitrag No.1, eingetragen 2019-09-23 10:06

Hallo apollonius und herzlich Willkommen auf dem Matheplaneten!

Ich habe jetzt keine Quelle parat, aber das mit der Paarbildung ist stets möglich (man denke nur an Ligen im Sport).

Soweit ich weiß, ist das Problem ein klassischer Fall für das Gebiet der diskreten Optimierung. Hier habe ich dir einmal einen älteren Thread zu dem Problem herausgesucht, wo ein solcher Algorithmus angesprochen wurde.


Gruß, Diophant



ochen
Senior
Dabei seit: 09.03.2015
Mitteilungen: 2864
Aus: der Nähe von Schwerin
Beitrag No.2, eingetragen 2019-09-23 11:06

Hallo,
ja, das geht. Die Frage wurde vor kurzem im Olympiade-Forum allgemeiner beantwortet. Aber hier steht es auch: math.stackexchange.com/questions/1172005/chromatic-index-of-a-complete-graph

Wir nummerieren die Personen von $0$ bis $21$. Wir betrachten die Person $21$ getrennt von den anderen. Weiter untersuchen wir $21$ 'perfekte Matchings', das sind die Runden. In der Runde $k$ (mit $1\leq k\leq 21$) sind $i$ und $j$ ein Paar (mit $i,j<21$), wenn $i+j-k$ durch $21$ teilbar ist.
In jeder Runde gibt es eine Person, die übrig bleibt. Es ist eben jene Person $i'$ für die $2i'-k$ durch $21$ teilbar ist. (Diese existiert, weil 21 nicht durch 2 teilbar ist.) Diese bildet ein Paar mit Person $21$.


Ich hoffe, dass ich mich nicht vertan habe.


OlgaBarati
Aktiv
Dabei seit: 16.11.2018
Mitteilungen: 189
Aus:
Beitrag No.3, eingetragen 2019-09-23 12:08

2019-09-23 08:58 - apollonius im Themenstart schreibt:
Hallo,

ich überlege gerade an folgendem Problem:

In einer Gruppe von 22 Personen sollen lauter Paare gebildet werden; da gibt es natürlich 231 Möglichkeiten.

In der ersten Runde werden nun 11 dieser Paare gebildet.
In der zweiten Runde werden 11 weitere mögliche Paare gebildet, usw.

Die Frage: ist es möglich, dass man in 21 Runden alle möglichen Paarungen realisiert? (Dabei darf/soll natürlich keine Paarung mehrfach vorkommen.)
Meine Vermutung ist: ja, das geht. (wie man sich für weniger als 22 Personen durch Ausprobieren schnell klarmacht)
Ich kanns aber nicht beweisen.
...
Vielleicht kommst Du für den ersten Teil deiner Frage damit weiter:
$N:=\text{Anzahl der Paarungen},\; n:=\text{Anzahl der Personen}$
$\;i:=\text{Nr. der Person}\;k:=2\text{/ Paar}$
$$N=\binom{n}{k}=\frac{n!}{k!(n-k)!}=\sum_{i=1}^{n-1}(n-i)=\frac{n^2-n}{2}=\overbrace{\frac{n}{2}}^{\text{Paare}}\cdot\overbrace{(n-1)}^\text{Anzahl Runden}$$ Ich hoffe auch dass ich mich nicht vertan habe  😄


apollonius
Neu
Dabei seit: 23.09.2019
Mitteilungen: 3
Aus:
Beitrag No.4, vom Themenstarter, eingetragen 2019-09-23 18:56

Hallo,

vielen Dank für die schnellen Antworten.
Die Methode von Ochen hab ich ausprobiert, wenn ich mich nicht vertan hab, scheint sie perfekt zu funktionieren :-)
Die anderen Links muss ich mir noch genauer ansehen.

Liebe Grüße


ochen
Senior
Dabei seit: 09.03.2015
Mitteilungen: 2864
Aus: der Nähe von Schwerin
Beitrag No.5, eingetragen 2019-09-24 12:19

Hallo,

wir betrachten erst einmal ein festes $k$, so ist die Beziehung der Personen $i$ und $j$ mit $21\mid i+j-k$ symmetrisch. Damit meine ich, dass aus $21\mid i+j-k$ auch $21\mid j+i-k$ folgt, da $i+j-k=j+i-k$ gilt. Es bildet dann und nur dann $i$ mit $j$ ein Paar, wenn auch $j$ mit $i$ ein Paar bildet.

Seien nun $i$ und $k$ fest, so bleibt zu zeigen, dass wir genau ein $j$ mit  $21\mid i+j-k$ finden. Unter den 21 aufeinander folgenden Zahlen $i+0-k, i+1-k, i+2-k, \ldots, i+20-k$ ist genau eine durch 21 teilbar. Wäre $i=j$, so folgt $21\mid 2i-k$ und wir weisen der Person $i$ die Person $21$ zu.
Wir haben also gezeigt, dass in jeder Runde 11 Paare entstehen (Jeder Person $i$ können wir einen Partner $j$ zuweisen und da die Beziehung symmetrisch ist, hat die Person $j$ auch Person $i$ als Partner).

Wir müssen noch zeigen, dass kein Paar in zwei unterschiedlichen Runden vorkommt. Seien also $i\neq j$ fest, so gibt es unter den 21 aufeinander folgenden Zahlen $i+j-1, i+j-2, i+j-3, \ldots, i+j-21$ ist genau eine durch 21 teilbar. Damit finden wir eindeutig ein $k$.

Es bleibt noch zu zeigen, dass es in jeder Runde $k$ ein $i$ mit $21\mid 2i-k$ gibt. Dies gilt, da $2i-k$ genau dann durch 21 teilbar ist, wenn $11(2i-k)$ durch 21 teilbar ist (warum?). Weiter ist $11(2i-k)$ genau dann durch 21 teilbar, wenn $11k-i$ durch 21 teilbar ist (warum?). Von den 21 aufeinanderfolgenden Zahlen $11k, 11k-1, 11k-2,\ldots,11k-20$ ist genau eine durch 21 teilbar. So finden wir eindeutig das $i$.



apollonius
Neu
Dabei seit: 23.09.2019
Mitteilungen: 3
Aus:
Beitrag No.6, vom Themenstarter, eingetragen 2019-09-29 18:08

Hallo,

vielen Dank für die ausführliche Antwort - da hab ich etwas, über das ich nachdenken kann :-)

Liebe Grüße




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=243609=70
Druckdatum: 2020-07-16 15:49