NWO finale 2026 vraag 2( klas 6)

Twintig teams moeten allemaal tegen elkaar spelen, maar per dag mogen slechts tien teams aanwezig zijn. Door eerst aanwezigheden te tellen en daarna een schema te construeren, vinden we het minimum.

Infobox

Onderwerpen: Combinatoriek, grafen
Probleemoplossingstechnieken: Dubbel tellen, een ondergrens bepalen, een constructie maken
Moeilijkheid: Gemiddeld
Competitie: Nederlandse Wiskunde Olympiade, finale, klas 6
Jaar: 2026
Opgavenummer: 2

Opgave

Twintig teams doen mee aan een toernooi waarbij ieder team precies één keer tegen ieder ander team speelt. Helaas is er per dag maar plek om tien teams uit te nodigen. Een team kan meerdere wedstrijden op één dag spelen en elke wedstrijd gaat tussen twee teams.

Hoeveel dagen zijn er minimaal nodig om het toernooi te houden?

Eerste idee

Elk team heeft negentien tegenstanders, maar kan er op één dag hoogstens negen ontmoeten. Tel daarom hoeveel aanwezigheden alle teams samen minstens nodig hebben. Verdeel vervolgens de teams in vier groepen van vijf om een schema te vinden dat die ondergrens bereikt.

Uitwerking

Waarom minstens zes dagen?

Elk team moet tegen de negentien andere teams spelen. Op één dag kan het hoogstens negen verschillende tegenstanders ontmoeten, omdat er maximaal tien teams aanwezig zijn.

In twee dagen kan een team dus hoogstens achttien tegenstanders ontmoeten. Elk team moet daarom op minstens drie dagen aanwezig zijn.

Voor de twintig teams zijn bijgevolg minstens

$20\cdot 3=60$

aanwezigheden nodig. Per dag zijn er hoogstens tien aanwezigheden, dus het aantal dagen is minstens

$\frac{60}{10}=6.$

Hoe volstaan zes dagen?

Verdeel de teams in vier groepen $A,B,C,D$ van elk vijf teams. Nodig op de zes dagen achtereenvolgens deze groepsparen uit:

$AB,\quad AC,\quad AD,\quad BC,\quad BD,\quad CD.$

Zo zijn er elke dag precies tien teams aanwezig.

Vier groepen van vijf teams, verbonden door zes lijnen: dag 1 AB, dag 2 AC, dag 3 AD, dag 4 BC, dag 5 BD en dag 6 CD.

Figuur 1. De vier knooppunten stellen de vier groepen van vijf teams voor. Elke lijn stelt één dag voor waarop de twee verbonden groepen samen aanwezig zijn. Elke groep is met de drie andere groepen verbonden en komt daardoor precies drie dagen.

De tekening vertaalt dit groepsschema naar een graafprobleem. De vier groepen zijn de knopen; tussen elk tweetal verschillende knopen ligt precies één ongerichte boog. Zo ontstaat de volledige graaf $K_4$ . Elke knoop heeft graad drie: er vertrekken drie bogen, één naar elke andere groep. De graaf is dus 3-regulier.

Bij het optellen van de graden tellen we elke boog twee keer, eenmaal bij elk eindpunt. Het aantal bogen is daarom

$\frac{4\cdot 3}{2}=6.$

Elke boog staat voor één dag waarop de twee verbonden groepen van vijf teams worden uitgenodigd. Dit geeft dus een schema met zes dagen. De vier knopen stellen groepen voor, geen afzonderlijke teams. Deze graaftelling bewijst dat zes dagen volstaan zodra ook de wedstrijden binnen de groepen worden ingepland, zoals hieronder. Dat minder dan zes dagen onmogelijk is, volgt uit de ondergrens hierboven; de graaftelling alleen bewijst die ondergrens niet.

Teams uit verschillende groepen spelen tegen elkaar op de unieke dag waarop hun twee groepen samen aanwezig zijn. Laat daarnaast alle wedstrijden binnen elke groep plaatsvinden op de eerste dag waarop die groep aanwezig is.

Voor $A$ en $B$ is dat dag 1, voor $C$ dag 2 en voor $D$ dag 3.

Hiermee speelt ieder tweetal teams precies één wedstrijd. Omdat meerdere wedstrijden per team per dag toegestaan zijn, voldoet dit schema aan alle voorwaarden.

Het minimum is dus

$\boxed{6\text{ dagen}}.$

Probleemoplossingstechnieken

Dubbel tellen: Tel de aanwezigheden per team en per dag.
Een ondergrens bepalen: Elk team moet minstens drie dagen aanwezig zijn.
Een constructie maken: Gebruik de zes paren van vier groepen van vijf teams.