Kombinatorik-Problem < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:38 So 18.06.2006 | | Autor: | M.Rex |
| Aufgabe | | Eine Universität lädt 16 Wissenschaftler zu einem Workshop ein. Er soll über mehrere Tage laufen, und zwar soll jeder Wissenschaftler genau einmal mit jedem Anderen einen Tag lang zusammenarbeiten. Wie viele Tage muss die Uni mindestens einplanen? (Workshops mit mehreren Teilnehmern gehen natürlich auch) |
Hallo,
Ich sitze schon seit einiger Zeit an dieser Aufgabe. Meine Vermutung ist, dass sie 9 Tage zusammensitzen müssen.
Schneller geht meiner Ansicht nach nicht.
Ich habe die Teilehmer mal im Hexadezimalsystem benannt, das erleichtert die Übersicht.
Meine 9-Tages Lösung:
1. Tag: 2 8er Workshops
{1,2,3,4,5,6,7,8} und {9,0,A,B,C,D,E,F}
2. - 9. Tag:
Je 8 Zweierworkshops,
2. Tag: {1,9} {2,0} {3,A} .... {8,F}
3. Tag: {1,0} {2,A} {3,B} .... {7,F} {8,9}
bis hin zu Tag 9: {1,F} {2,9} {3,0} ...{7,D} {8,E}.
Geht das eventuell auch schneller?
Ich habe schon versucht, die ersten vier Tagen jeweils mit Vierergruppen anzufangen, aber ich komme auch auf 9 Tage.
Mit unsymmetrischen Verteilungen anzufangen, spart meiner Meinung nach auch keinen Tag (1 Vierergruppe und 4 Dreiergruppen).
Für Ideen wäre ich Dankbar.
Marius
Ich habe diese Frage nirgends sonst gestellt.
|
|
| |
|
Hallo und guten Tag,
ich würd die Aufgabe so verstehen, dass jeder Wissenschaftler pro tag nur mit höchstens einem anderen zusammenarbeiten kann,
dass aber durchaus mehrere Pärchen parallel an einem Tag arbeiten können.
Dann reichen aber 15 Tage - und soviele braucht man auch.
Dass 15 notwendig sind, folgt aus obigem. Dass sie reichen, sieht man, indem man am Tag i (Wissenschaftler seien 0-15 durchnumeriert)
die Paare [mm] (a,a+i\mod [/mm] 16) bildet.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:57 Di 27.06.2006 | | Autor: | M.Rex |
| Aufgabe | | Eine Universität lädt 16 Wissenschaftler zu einem Workshop ein. Er soll über mehrere Tage laufen, und zwar soll jeder Wissenschaftler genau einmal mit jedem Anderen einen Tag lang zusammenarbeiten. Wie viele Tage muss die Uni mindestens einplanen? (Workshops mit mehreren Teilnehmern gehen natürlich auch) |
Hallo,
Ich habe mal versucht, das obige Problem allemein zu lösen.
Nehmen wir mal an, wir haben n Teilnehmer (n gerade, n [mm] \ge [/mm] 4).
Dann braucht man mindestens [mm] \bruch{n}{2} [/mm] +1 Tage.
Die Aufteilung ist dann folgendermassen:
1. Tag.
Gruppe 1: [ [mm] 1,2,....\bruch{n}{2} [/mm] ]
Gruppe 2: [ [mm] \bruch{n}{2} [/mm] +1 , ...., n ]
An den anderen Tagen gibt es jeweils Zweierworkshops, man braucht noch
[mm] \bruch{n}{2} [/mm] Tage.
Meine Frage ist jetzt:
Ist die Überlegung richtig, oder geht es evtl. doch mit weniger Tagen?
Wenn jemand ein Gegenbeispiel angeben kann ist das auch okay.
Marius
|
|
|
| |
|
Moin Marius,
nochmal als Kommentar zu dieser Loesung: Dann koennte man auch alle an einem Tag in eine Gruppe
packen, meiner Ansicht nach ist das aber so nicht gemeint, sondern so, dass man Zweiergruppen bilden soll,
aber bei 2n Wissenschaftlern jeden Tag n paarweise disjunkte Zweiergruppen bilden darf.
Gruss,
Mathias
|
|
|
|
