Die Mathe-Redaktion - 19.10.2019 04:38 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 143 Gäste und 3 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Kombinatorik & Graphentheorie » Alle Paare bilden
Druckversion
Druckversion
Autor
Universität/Hochschule J Alle Paare bilden
apollonius
Neu Letzter Besuch: im letzten Monat
Dabei seit: 23.09.2019
Mitteilungen: 3
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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 smile

Liebe Grüße



  Profil  Quote  Link auf diesen Beitrag Link
Diophant
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.01.2019
Mitteilungen: 1916
Aus: Rosenfeld, BW
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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




  Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2358
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.



  Profil  Quote  Link auf diesen Beitrag Link
OlgaBarati
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 16.11.2018
Mitteilungen: 178
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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  smile


-----------------
oLGa



  Profil  Quote  Link auf diesen Beitrag Link
apollonius
Neu Letzter Besuch: im letzten Monat
Dabei seit: 23.09.2019
Mitteilungen: 3
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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



  Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2358
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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$.




  Profil  Quote  Link auf diesen Beitrag Link
apollonius
Neu Letzter Besuch: im letzten Monat
Dabei seit: 23.09.2019
Mitteilungen: 3
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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



  Profil  Quote  Link auf diesen Beitrag Link
apollonius hat die Antworten auf ihre/seine Frage gesehen.
apollonius hat selbst das Ok-Häkchen gesetzt.
apollonius wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


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-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]