Rätsel

By Thorsten Poeppe Date 2009-07-24 11:14

Hallo!

Früher (vielleicht auch noch jetzt) gab es in der CSS zeitweise eine Rätsel-Ecke, die sehr beliebt war.

Ich stehe gerade vor einem mathematischen Problem, das ich Euch gerne vorstellen möchte. Vielleicht hat ja jemand eine Lösung dafür. Ich selbst habe noch keine Lösung gefunden.

Es gibt zwölf Personen (1-12), die an 12 Terminen zusammen Gruppenarbeit
betreiben sollen.

Pro Termin können aus Platzgründen jedoch immer nur 6 Personen
eingeladen werden.

Die Teilnehmer sollen alle gleich oft eingeladen werden und möglichst
immer "gut gemischt" werden.

Jeder Teilnehmer wird somit 6x eingeladen und sollte minimal 2x und
maximal 3x mit jedem anderen Teilnehmer zusammen einen Termin belegen.
(Jeder trifft somit je dreimal auf acht Teilnehmer und je zweimal auf
drei Teilnehmer.)

Wer kann mir für die 12 Termine "Teilnehmerlisten" erstellen, bei denen
die o. g. Kriterien erfüllt sind?

Mathematisch oder programmiertechnisch fehlen mir die Kenntnisse, um das Problem zu lösen. Bisher habe ich es nur mit Ausprobieren versucht, aber noch keine Lösung gefunden. Mittlerweile bin ich mir auch nicht mehr sicher, ob es überhaupt eine Lösung gibt.

Kann mir jemand helfen?

Vielen Dank für Eure Hilfe.

Gruß,

Thorsten Pöppe

By Wolfram Bernhardt Date 2009-07-27 12:35

Hallo!

Interessantes Problem. Ich hab vorhin ein kleines stumpfes Programm geschrieben, das seit dem nach der Lösung sucht.
Bisher hat es aber nicht einmal eine Lösung für 9 Termine gefunden (mit ansonsten gleichen Rahmenbedingungen).
Gut, vielleicht sollte ich es noch cleverer machen...

Woher kommt die Aufgabe? Und - gibt es eine Möglichkeit, festzustellen, ob es eine Lösung gibt?

Viele Grüße,
Wolfram

By Thorsten Poeppe Date 2009-08-01 11:25

Hallo!

Ich möchte ein Dart-Turnier nach diesem Schema spielen lassen. Das Problem liegt darin, dass nicht zwölf Teilnehmer gleichzeitig spielen können und für mehrere Runden die Zeit fehlt.

Ob es überhaupt eine Lösung gibt, weiß ich nicht. Falls nicht irgendwer eine Lösung finden sollte, wird sich die Frage wohl auch nicht beantworten lassen.

Thorsten

By Wolfram Bernhardt Date 2009-08-02 00:00

Tja... warten wirs ab. Ich hab mich heute nochmal hingesetzt und ein erheblich besseres (und vor allem schnelleres) Programm geschrieben. Es läuft seit 18.00 Uhr, schafft 500.000 sinnvolle "Stellungen" pro Sekunde, aber hat noch nichts gefunden. gefühlsmäßig dachte ich, es ginge, aber mir kommen langsam Zweifel... ich frickel mal einfach weiter...

Ciao,
Wolfram

By Urs Maier Date 2009-08-04 00:23

kannst du dein programm mal posten?

By Franz Huber Date 2009-08-02 21:00

Hallo Thorsten,

ja, es gibt (viele) Lösungen - versuch's mal mit folgender Spieltabelle:

Code:


   A B C D E F G H I J K L
01 + + + + o o + o o + o o
02 + + + o + o o + o o + o
03 + + + o o + o o + o o +
04 + o o + + + o + o o o +
05 o + o + + + o o + + o o
06 o o + + + + + o o o + o
07 + o o o o + + + + o + o
08 o + o + o o + + + o o +
09 o o + o + o + + + + o o
10 + o o o + o o o + + + +
11 o + o o o + + o o + + +
12 o o + + o o o + o + + +

A-L sind die Spieler, 01-12 die einzelnen Runden - allerdings kannst
Du Zeilen und Spalten auch vertauschen, da ich die Matrix symmetrisch
konstruiert habe. ('+' heißt Teilnahme, 'o' nicht)

Ich hoffe, es war so gemeint: jeder sollte genau 6-mal spielen und mit
jedem anderen entweder 2- oder 3-mal zusammentreffen!?

Und das alles ohne Computerhilfe - nur die von mir erstellte Tabelle
habe ich dann mit einem Programm überprüft, ob auch wirklich alle
Bedingungen erfüllt sind - hier das Ergebnis (wer mit wem wie of spielt):

Code:


  A B C D E F G H I J K L
A 6 3 3 2 3 3 2 3 3 2 3 3
B 0 6 3 3 2 3 3 2 3 3 2 3
C 0 0 6 3 3 2 3 3 2 3 3 2
D 0 0 0 6 3 3 3 3 2 3 2 3
E 0 0 0 0 6 3 2 3 3 3 3 2
F 0 0 0 0 0 6 3 2 3 2 3 3
G 0 0 0 0 0 0 6 3 3 3 3 2
H 0 0 0 0 0 0 0 6 3 2 3 3
I 0 0 0 0 0 0 0 0 6 3 2 3
J 0 0 0 0 0 0 0 0 0 6 3 3
K 0 0 0 0 0 0 0 0 0 0 6 3
L 0 0 0 0 0 0 0 0 0 0 0 6

Wie man sieht geht's also auch mit der 'Bio-CPU'!

Grüße,
Franz.

By Wolfram Bernhardt Date 2009-08-03 20:09

Ja, klasse, das haut hin.

Mein dusseliges Programm rechnet immer noch, aber das kann ich dann jetzt wohl abbrechen

Ciao,
Wolfram

By Franz Huber Date 2009-08-09 21:17

[quote="Franz Huber"]
Hallo Thorsten,
ja, es gibt (viele) Lösungen - versuch's mal mit folgender Spieltabelle:

...
[/quote]
Ist schon interessant, daß derjenige, der dieses Rätsel gepostet hat
(und angeblich auch an einer Lösung interessiert war), es dann nach
dem Lösen der Aufgabe nicht einmal der Mühe wert findet, sich irgendwie
dazu zu äußern!

Da wird man sich in Zukunft wohl dreimal überlegen, ob man sich in einer
solchen Situation nochmals einige Stunden mit so einem Problem beschäftigt ...

By Thorsten Poeppe Date 2009-08-21 18:17

Hallo, Franz!

Ich bin gestern erst aus dem Urlaub zurückgekommen und habe mir zweieinhalb Wochen eine Internet freie Zeit gegönnt.
Umso erfreuter war ich, als ich jetzt die Lösung meines Problems gelesen habe. Deine Lösung passt tatsächlich. Ich habe es nicht mehr für möglich gehalten.

Dass Du enttäuscht darüber warst/bist, nicht gleich eine Antwort zu erhalten, tut mir Leid.

Trotzdem möchte ich mich bei Dir und all den anderen, die für eine Lösung Zeit investiert haben, natürlich bedanken. Ich hoffe, Du kannst den Grund dafür verstehen.

Thorsten