JAARROOSTER DARTCOMPETITIE

Onlangs kreeg ik bij Wisfaq een interessante vraag over een jaarrooster voor een dartcompetitie. Dit soort vragen wordt vaak gesteld. Een medebeantwoorder plaatste er zelfs als commentaar bij: 'gat in de markt'. Nou ja, wiskundige ingenieursbureau's kunnen zulke vragen natuurlijk ook wel beantwoorden.

De vraag luidde:
Beste Wisfaqbeantwoorder. Ik zit op een dartvereniging. Deze organiseert een competitie. De vereniging heeft 24 mensen en 8 dartborden. Dit houdt in dat er groepjes van drie worden gevormd. Het probleem is nu echter dat je vaak tegen dezelfde speler speelt, en tegen een ander bijna nooit. Zelf heb ik wel eens geprobeerd om hiervoor iets te vinden, maar dit is tot op heden niet gelukt. Is hiervoor toevallig een mooi systeem voor, of wiskundige software om dit op te lossen? Met vriendelijke groet, Alexander.

Mijn antwoord:
Hallo, Alexander. Pas brute rekenkracht toe, als volgt:

Declareer in Pascal: groep=array[1..40,1..24] of 1..8 {groep[k,n] is groepnummer van speler nummer n op avond nummer k}.
Je moet het volgende programma heel precies intypen met de Pascal editor (of gebruik de kopieerfuncties).
Daarna compileren. Als je een typfoutje gemaakt hebt, krijg je de gelegenheid om dat te verbeteren.
Save het programma onder de naam competitie.pas .
Tenslotte runnen. De output verschijnt op je scherm (zorg dat het scherm breed genoeg is).
Het volledige programma luidt:

program competitie;
var minimum,k,l,m,n,p,k1,k2,n1,n2:integer; groep:array[1..40,1..24] of 0..8;
begin
minimum:=10000;{initialisatie}
repeat
for k:=1 to 40 do
begin
for n:=1 to 24 do groep[k,n]:=0;{initialisatie}
for l:=1 to 8 do for m:=1 to 3 do
begin repeat n:=1+random(24) until groep[k,n]=0; groep[k,n]:=l end
end;
p:=0;{teller van doublures}
for k1:=1 to 40 do for k2:=k1+1 to 40 do
for n1:=1 to 24 do for n2:=n1+1 to 24 do
if ((groep[k1,n1]=groep[k1,n2]) and (groep[k2,n1]=groep[k2,n2]))
then p:=p+1;
if not p ≥ minimum then begin
minimum:=p;
writeln;writeln(p:7);
for k:=1 to 40 do
begin
writeln('avond',k:3);write('***');
for n:=1 to 24 do write(n:3,groep[k,n]:2,'*');
writeln
end
end
until false
end.

Wacht nu geduldig tot er een jaarrooster uitrolt waar je blij mee bent.

(Na een paar uur runnen krijgen we een rooster met 1452 doublures.
Aangezien er voor elke week vierentwintig paren (k1,k2) met k1 kleiner dan k2 getrokken worden waarbij k1 en k2 in eenzelfde groep zitten, en voor een andere week de kans dat k2 in dezelfde groep komt als k1 gelijk is aan 1/8, is het verwachte aantal doublures 24*(1/8)*40*39/2 = 2340.
We krijgen door het programma dus een reductie van het aantal doublures met 38 percent ten opzichte van het verwachte aantal. Als je het programma niet gebruikt, heb je al gauw twee keer zoveel doublures dan met het programma.)