WisFaq!

Handleiding opstellen voor volleybaltornooi

Beste WisFaq,

Al enkele weken probeer ik een antwoord te vinden op het volgende:
Maak een handleiding voor het maken van speelschema's voor een volleybaltornooi met een nog onbekend aantal deelnemende teams. De teams spelen een halve competitie, dat wil zeggen: ieder team speelt één keer tegen ieder ander team. Je beschikt over twee velden.
Maak een speelschema zodat het tornooi zo kort mogelijk duurt.

Ik ben hieraan begonnen door een piramide op te stellen met de wedstrijden die moeten gespeeld worden met 5 ploegen (elke letter stelt een ploeg voor):
AB BC CD DE
AC BD CE
AD BE
AE

Oplossing:
(1x alfabet volgen, dan de piramide horizontaal afgaan met de wedstrijden die nog overblijven)
veld 1 veld 2
AB CD
EA BC
DE AC
BD CE
AD BE

(Deze methode is analoog voor 7, 9, 11, ... dus oneven ploegen. Alleen zal je hierbij 2x alfabet moeten volgen en dan de piramide horizontaal afgaan met de wedstrijden die nog overblijven.)

Voor 6 en andere even aantal ploegen heb ik de ploegen gerangschikt in groepjes van twee en telkens twee groepjes onderling laten spelen. De groepjes zijn als volgt:
groep 1: A en B
groep 2: C en D
groep 3: E en F

Oplossing:
veld 1 veld 2
AC BD (groep 1 en 2)
AD BC (groep 1 en 2)
CF DE (groep 2 en 3)
CE DF (groep 2 en 3)
AE BF (groep 1 en 3)
AF BE (groep 1 en 3)
AB CD (groep 1 op veld 1 en groep 2 op veld 2)
EF (groep 3)

(Deze methode bleek analoog te zijn voor alle andere even ploegen.)

Tot hier is het me gelukt. Het vervolg is voor mij echter een raadsel en luidt als volgt:
Men besluit om aan het toernooireglement de beperking toe te voegen dat een team hooguit TWEE wedstrijden achter elkaar speelt en daarna minimaal een ronde moet overslaan om te pauzeren. Maak een speelschema voor het toernooi dat zo kort mogelijk duurt, op twee velden plaatsvindt en voldoet aan deze nieuwe beperking. Doe dit eerst voor vijf teams en vervolgens voor een willekeurig aantal teams.

(Wanneer je hierin slaagt, probeer dan een mogelijk speelschema op te stellen voor 13 ploegen waarin je beschikt over 12 velden die niet allemaal gebruikt moeten worden. Hoe meer velden je gebruikt, hoe meer hoe je moet betalen en je wil natuurlijk de kosten zo laag mogelijk houden. Laat het toernooi zo kort mogelijk duren en blijf eveneens rekening houden met de beperking van hierboven.)

Kunnen jullie me hierbij helpen?
Alvast bedankt!

Kaat Somers
14-4-2011

Antwoord

Hallo, Kaat.

Dit kan men oplossen met "eindeloos lukraak proberen" mbv een pascalprogramma.
Voor 5 ploegen op 2 velden zijn er door de pauzebeperking zes ronden nodig.
Een mogelijk speelschema is:

ronde 1: 4-5 2-3
ronde 2: 1-2 3-5
ronde 3: 1-4
ronde 4: 2-5
ronde 5: 2-4 1-3
ronde 6: 1-5 3-4

De programmacode luidt:

program volley;
var m,n,r,v,i,j,k,l,s,t,aantalronden:integer; mogelijk,klaar:boolean;
aantal:array[1..100,1..13] of 0..100;
ronde, veld:array[1..100,1..13] of 1..100;
begin
writeln('aantal ploegen?'); readln(m);
writeln('aantal velden?'); readln(n);
aantalronden:=m*(m-1) div 2;
while true do
begin
aantalronden:=aantalronden-1;
repeat
mogelijk:=true;
for r:=1 to aantalronden do for v:=1 to n do aantal[r,v]:=0;
for i:=1 to m do for j:=i+1 to m do
begin
ronde[i,j]:=random(aantalronden)+1; veld[i,j]:=random(n)+1;
ronde[j,i]:=ronde[i,j]; veld[j,i]:=veld[i,j];
s:=ronde[i,j];t:=veld[i,j];
aantal[s,t]:=aantal[s,t]+1
end;
for i:=1 to m do for j:=1 to m do for k:=1 to m do
if ((ij) and (ik) and (jk)) then
if ronde[i,j]=ronde[i,k] then mogelijk:=false;
for i:=1 to m do for j:=1 to m do for k:=1 to m do for l:=1 to m do
if ((ij) and (ik) and (il) and (jk) and (jl) and (kl)) then
if (abs(ronde[i,j]-ronde[i,k])2) and (abs(ronde[i,j]-ronde[i,l])2)
then mogelijk:=false;
if mogelijk then
for r:=1 to aantalronden do for v:=1 to n do if aantal[r,v]1
then mogelijk:=false;
if mogelijk then klaar:=true else klaar:=false;
if klaar then for i:=1 to m do
begin
writeln; for j:=i+1 to m do write(i:3,j:3,ronde[i,j]:3,veld[i,j]:3,'***')
end
until klaar
end
end.

Voor 13 ploegen en 12 velden is mijn programma nog aan het runnen.
Zodra er geschikte output is, zal ik die hier onderaan toevoegen.

hr
15-4-2011