Mathematische Lösung gesucht

lunivo

Grünschnabel
Hallo,

ich habe leider keine passendere Rubrik gefunden und da ich selber Entwickler bin und es sich hierbei um ein Problem in meiner Software handelt, habe ich diese Rubrik gewählt.

Vorab - ich habe die Problemstellung etwas versinnbildlicht, damit man besser durchsteigt.

Also:

Es gibt 8 Leute, die sich jeweils zu zweit an vier verschiedenen Orten treffen sollen - Es resultieren also vier Gruppen. Jeder Soll jeden Ort einmal gesehen haben dabei aber immer den Partner wechseln.
Keiner darf an einem Ort zwei Mal gewesen sein UND keiner darf zwei mal mit dem selben Partner unterwegs sein.

Das heißt also, dass jeder vier Mal unterwegs ist und immer einen anderen Partner bei sich hat.

Ich bin mir ziemlich sicher, dass dieses Problem nicht lösbar ist - ich kann das aber leider nicht wissenschaftlich belegen. Ich finde einfach keine Mathematische Begründung. Oder geht es doch und ich komme einfach nicht drauf?

Ich würde mich sehr freuen, wenn mir hier jemand helfen könnte.

Vielen Dank im Voraus!
 

Spyke

Premium-User
Ich finde eher es wäre lösbar, nur beweisen kann ichs grad auch nicht wirklich.

Vielleicht bin ich auch grad bissel verwirrt und es ist schon spät, aber könntens nicht auch 16 Gruppen sein? ? ?
Sry, steh grad selbst aufn schlauch.
 

lunivo

Grünschnabel
Es sind 8 Leute - zu zweit werden Gruppen gebildet. Nach dem Besuch eines Ortes treffen sich die Leute erneut und Mischen neu durch. Es gibt also immer vier neue Gruppen, die in dieser Konstellation nicht vorher schon einmal unterwegs waren. So arbeiten dann alle Leute alle Orte mit jeweils anderen Partnern ab.

Wichtig sind ist die Einhaltung der Parameter:
- Jeder Soll jeden Ort einmal gesehen haben dabei aber immer den Partner wechseln.
- Keiner darf an einem Ort zwei Mal gewesen sein UND keiner darf zwei mal mit dem selben Partner unterwegs sein.
 

chmee

verstaubtes inventar
Premium-User
Wenn ich alle Betreffenden (Ort, Mensch, Mensch) als Nummern abstrahiere, sehe ich auf Anhieb eine Dreinummernfolge, die in 4 Variationen erscheinen soll.

Beispielkombination
1 15 - 2 26 - 3 37 - 4 48
1 46 - 2 17 - 3 28 - 4 35
1 34 - 2 45 - 3 16 - 4 27 (<= Fehler 4 in 1 und 2)
1 27 - 2 38 - 3 45 - 4 16


Hab ich das so richtig verstanden? Ist ein bisschen Sudoku :D Hmm. Mathematischer Beweis bzw Gegenbeweis..

mfg chmee
 

sheel

I love Asm
Bei dir kommt zB. in der zweiten Zeile der Mensch 1 zweimal vor, also nein.
edit: Ok, jetzt sinds andere Nummern :)
Jetzt wären zB. 1 und 6 mehrmals zusammen

8 Leute, 4 Termine, 4 Orte.
Je zwei Leute besuchen pro Termin einen Ort.
Ein Mensch muss jeden Ort genau einmal besuchen
und darf nicht mehrmals mit dem selben Partner irgendwo sein.
 

chmee

verstaubtes inventar
Premium-User
[stimmt] Na, ich wollte jetzt keinen Beweis liefern, aber ne bildhafte und eigentlich recht spaßige Umsetzung des Problems aufzeigen..

edit. Stichwort Sudoku. Der von Dir gezeigte Fehler hat die letzte Zeile aufgelöst :) Dafür hab ich noch nen Fehler in der dritten Zeile gefunden. Bin müde. Viel Spaß :)

mfg chmee
 

sheel

I love Asm
Sudoku:
Code:
-x0x0x0x
x-x0x0x0
0x-x0x0x
x0x-x0x0
0x0x-x0x
x0x0x-x0
0x0x0x-x
x0x0x0x-
Bitte sehr, alle x ausfüllen
Genau einmal 1,2,3,4 pro Zeile und Spalte,
und zwar so, dass es an der Diagonale spiegelbar bleibt
:D
 

HonniCilest

Erfahrenes Mitglied
Ich hätte einen Ansatz, ich weiß nur nicht ob ich den verständlich rüberbringen kann ;-)

Stell dir tatsächlich ein Sudoku vor. Um die Zellen zu füllen benötigst du eine imaginäre 9. Person.
Gruppe 1-3 entsprechen nun jeweils den ersten 2 Spalten eines Sudoku-Kastens. Die jeweils 3. Spalte ist die Gruppe 4 + Person 9. Die Person 9 muss nun in den ersten 3 Zeilen in einer anderen Spalte stehen unabhängig davon wie die anderen 8 Personen veteilt sind. Hier stößt du dann in Zeile 4 auf das Problem. Alle 3 Spalten wo die 9 stehen darf sind schon belegt, d.h. Person 9 müsste in eine der Gruppen 1-3 rutschen.

Jede Zeile entspricht hierbei einem Termin.

Oder entsprechend versinnbildlicht ;-)
Person 1-8 sind Schüler und Person 9 ist ein Lehrer. Die ersten 3 Gruppen entsprechen einem Ausflug in ein Museum und Gruppe 4 bleibt beim Lehrer um über mathemtische Probleme zu reden :D Jeder Schüler soll natürlich möglichst viele andere Klassenkameraden kennenlernen. Am Tag 4 geht das Konzept dann nicht mehr auf, da der Lehrer ins Musuem gehen müsste.
 
Zuletzt bearbeitet: