Competitie schema probleem

Wiskunde is niet alleen een vak op school. Kom je ergens in de praktijk (bijvoorbeeld tijdens je werk) een wiskundig probleem tegen dan kun je hier om hulp vragen.
Plaats reactie
Sjorty
Nieuw lid
Nieuw lid
Berichten: 2
Lid geworden op: 08 sep 2014, 12:16

Competitie schema probleem

Bericht door Sjorty » 08 sep 2014, 12:22

Ik hoop dat er hier slimme mensen rond lopen die mij kunnen helpen met een probleem.
Op een spelletjes site, www.turnbasedbordspellen.nl, ben ik de toernooi organisator. Het gaat hier om bordspellen die digitaal te spelen zijn.
Nou ben ik bezig met een toernooi voor een spel, waarbij je met z'n 4-en in 1 speelt. Voor dit toernooi hebben zich 20 mensen aangemeld. Ik wilde eigenlijk 2 poules van 10 maken waarin iedereen 2x tegen iedereen speelt. In 1 spel speel je tegen 3 anderen, dus met 6 spelletjes per persoon zou je tegen iedereen 2x gespeeld moeten kunnen hebben. Nou probeer ik hier een schema voor te maken. Maar ik kom er niet uit en hoopte dat iemand hier wellicht een briljante ingeving had. Of is dit simpelweg trial and error?

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Competitie schema probleem

Bericht door arie » 08 sep 2014, 18:29

Meestal lossen we dit soort problemen op door (systematisch) zoeken.
Een mogelijke oplossing (spelers genummerd van 1 t/m 10):

(1, 2, 3, 4 )
(1, 2, 5, 8 )
(1, 3, 6, 9 )
(1, 4, 7, 10)
(1, 5, 6, 7 )
(1, 8, 9, 10)
(2, 3, 5, 10)
(2, 4, 6, 9 )
(2, 6, 7, 8 )
(2, 7, 9, 10)
(3, 4, 7, 8 )
(3, 5, 7, 9 )
(3, 6, 8, 10)
(4, 5, 6, 10)
(4, 5, 8, 9 )

Dit zijn 15 wedstrijden, waarbij iedere wedstrijd gespeeld wordt met 4 spelers, iedereen 6 wedstrijden speelt, en iedereen elke andere speler precies 2 keer tegenkomt.

Sjorty
Nieuw lid
Nieuw lid
Berichten: 2
Lid geworden op: 08 sep 2014, 12:16

Re: Competitie schema probleem

Bericht door Sjorty » 09 sep 2014, 12:07

Dank je Arie. Ik zal eerlijk zeggen dat ik 15 minuten na m'n post, zelf met enig puzzelen een oplossing had gevonden. Maar had de dagen daarvoor zonder succes gepuzzeld.
Maar er is dus niet een soort algoritme voor begrijp ik. Gewoon systematisch zoeken.

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Competitie schema probleem

Bericht door arie » 09 sep 2014, 16:52

Mooi dat het je al gelukt was !

Voor sommige toernooivormen bestaan er snelle oplossingen, zie bijvoorbeeld
http://en.wikipedia.org/wiki/Round-robin_tournament,
maar voor andere niet.

Jouw probleem is een variant van het Social Golfer Problem, zie bv paragraaf 2 van
http://cs.brown.edu/~pvh/sst.pdf,
waarbij in jouw geval de spelers elkaar niet maximaal 1 keer maar precies 2 keer tegenkomen.

Zeker als er ook nog aanvullende eisen (constraints) bij komen zullen we in eerste instantie terugvallen op heuristische zoekmethoden uit de informatica, zie bv
http://nl.wikipedia.org/wiki/Zoekalgoritme,
die in redelijke tijd een redelijke oplossing geven.

Plaats reactie