Hallo, ik kreeg laatst dit probleem voorgeschoteld:
Een groep mensen wil met zijn allen een toernooi organiseren waarin er een gezelschapsspel (zoiets als Risk) meerdere malen wordt gespeeld. Het spel wordt altijd met 4 personen gespeeld en er zijn 3 spellen beschikbaar. De groep bestaat dan ook uit 12 deelnemers zodat iedereen in een ronde precies verdeeld kan worden over de spellen. De vraag is: hoeveel rondes moeten er minimaal gespeeld worden zodat ieder tweetal deelnemers tenminste één keer bij elkaar is ingedeeld (d.w.z. tegen elkaar gespeeld heeft)? En wat wordt dan het speelschema?
Tot slot: bestaat er een manier om het kortst mogelijke speelschema te maken als het aantal spellen en het aantal deelnemers per spel onbekend is?
Arno
Student universiteit - woensdag 4 december 2002
Antwoord
Hallo Arno,
Lijkt een simpel vraagje, maar schijn bedriegt... Er zijn 12 personen, dus 12·11/2 = 66 koppels. Per ronde (= 3 spellen) kan je 3·6 = 18 koppels maken, dus een strikt minimum is zeker 4 rondes (met 3 kom je maximaal aan 54 koppels, met 4 kom je aan 72 koppels dus mag je 6 koppels dubbel gebruiken). Echter, in 4 rondes wordt het zeer moeilijk: noem de mensen a tot l en vertrek met abcd, efgh, ijkl. Voor de volgende ronde moet je per viertal al zeker twee mensen samenzetten die in de vorige ronde samenspeelden, je verliest dus al 3 koppels (probeer maar: kies a, samen met e, samen met i, samen met ??). De ronde daarna zal je hetzelfde probleem nog eens hebben, dus je ziet in dat je er met 4 rondes (volgens mij) niet zal komen. Met 5 wel, zoals volgende ietwat saaie oplossing aantoont:
Saai, want a speelt altijd samen met b, c altijd met d enzovoort. Maar ik heb er zo mijn twijfels bij of er een andere oplossing is (er een computerprogramma op los laten lijkt me de beste oplossing). Het andere uiterste, wanneer elk koppel even vaak voorkomt, zal misschien wat lang duren: 66 koppels, 18 koppels per ronde, dus moet je 11 rondjes spelen en komt elk koppel drie maal voor, en daarvoor bestaat waarschijnlijk een mooi symmetrische oplossing.
En voor die slotvraag moet ik helemaal passen. Je kan natuurlijk altijd je aantal koppels uitrekenen en zo tot een strikt minimum komen, en misschien dat je voor mooi deelbare getallen een analoge tactiek kunt volgen (dus steeds koppels samenzetten), maar dat zijn maar wilde gissingen.
