WisFaq!

Speelschema

Voor ruim honderd jonge mensen organiseer ik binnenkort een zeskamp. De groep is verdeeld in 12 teams. Er zijn 6 verschillende spellen (genaamd A t/m F), waarbij telkens 2 teams tegen elkaar strijden. Er zijn dus 6 rondes nodig om alle teams de zes spellen te laten spelen. Ik zoek een speelschema dat voldoet aan de volgende voorwaarden:

• Elk team speelt elk spel maar één keer
• Elk team moet alle spellen spelen
• Elk team moet elke ronde tegen een ander team strijden, dus mag niet twee keer tegen hetzelfde team spelen (hierin zit de complicatie!)

Ik ben al dagen aan het proberen een kloppend speelschema te ontwikkelen, maar ik krijg het niet voor elkaar...

Ik heb wel een schema gevonden maar dat is niet bruikbaar, omdat in genoemd schema alle zes ronden hetzelfde spel gespeeld wordt (namelijk voetbal). In de zeskamp die ik organiseer speelt elk team iedere ronden een verschillend spel. Daarin zit juist de complicatie; het is natuurlijk niet leuk als een team twee keer hetzelfde spel speelt.

Zouden jullie mij kunnen helpen aan een kloppend schema dat aan de genoemde voorwaarden voldoet?

Alvast hartelijk dank!

Verheul
3-3-2009

Antwoord

Houd er rekening mee dat dit soort problemen niet oplosbaar hoeft te zijn. In jouw geval vermoed ik dat het 5 ronden goed kan gaan maar dat het in ronde 6 fout loopt. Zoiets valt niet te bewijzen of te berekenen. Er is ook geen algoritme dat je met dit soort randvoorwaarden verder helpt. Dus sta toe eventueel toe dat het speelschema niet helemaal aan je eisen voldoet. Ik ben wel benieuwd hoever je zelf bent gekomen.

Mijn vermoeden was blijkbaar iets te pessimistisch. Met de hand was ik al gekomen tot nog maar twee foutjes in de combinaties. Inmiddels heeft Lieke een computersimulatie geschreven en toch een oplossing gevonden. Ik geef even het resultaat.

1. 012345
2. 021453
3. 102534
4. 130425
5. 204351
6. 235104
7. 345012
8. 351240
9. 423510
10. 450132
11. 514023
12. 543201

De 12 teams zijn weekgegeven met de letters A t/m L. De spelen zijn aangegeven met de cijfers 0 t/m 5. De eerste kolom is spelronde 1 Dan spelen team A en B spel 0 tegen elkaar. In elke kolom komt elk spel precies twee keer voor, elk team speelt elk spel en speelt nooit twee keer tegen het zelfde team.

Dit is dus opgelost met een computersimulatie. Er zijn misschien nog meer oplossingen. Maar het programma stopt bij de eerste gevonden oplossing.

Bedankt Lieke voor je input.

Met vriendelijke groet
JaDeX

jadex
11-3-2009