Twee punten verschil

Twee punten verschil

Op 15 september 2017 vond de finale van de Nederlandse Wiskunde Olympiade plaats. De 159 deelnemers kregen drie uur de tijd om te werken aan vijf pittige opgaven. In dit artikel wordt de derde opgave van deze wedstrijd besproken.

FINALE NEDERLANDSEWISKUNDE OLYMPIADE 2017, OPGAVE 3

Aan een hockeytoernooi doen zes teams mee. Elk team speelt precies één keer tegen elk ander team. Voor een gewonnen wedstrijd krijgt een team 3 punten, voor een gelijkspel 1 punt en voor een verloren wedstrijd 0 punten. Aan het einde van het toernooi wordt een ranglijst opgemaakt. Er blijken geen gedeelde plaatsen op de ranglijst voor te komen. Ook blijkt dat elk team (behalve het team dat laatste is geworden) precies 2 punten meer heeft dan het team dat één plaats lager staat. Bewijs dat het team dat als vierde geëindigd is, precies twee wedstrijden gewonnen heeft.

Bij Olympiade-opgaven kan het altijd helpen om een klein voorbeeld te bekijken, waardoor we ideeën krijgen voor de oplossing. Bij deze opgave kunnen we bijvoorbeeld kijken wat er gebeurt als het zesde team 0 punten heeft. Dan heeft het vijfde team dus 2 punten, het vierde team 4 punten, het derde team 6 punten, het tweede 8 punten en het beste team 10 punten. We weten nu al veel over het laatste team: omdat dit team geen punten heeft, heeft het alle wedstrijden verloren. Het vijfde team heeft dus gewonnen van het laatste team en heeft dus minstens 3 punten. Maar het vijfde team heeft maar 2 punten, dus dit levert een tegenspraak. We kunnen ook kijken naar een geval waarin het laatste team veel punten heeft gehaald, bijvoorbeeld 10. Het vijfde team heeft er dan 12, het vierde team 14, het derde team 16, het tweede team 18 en het beste team 20. Omdat elk team maar vijf wedstrijden speelt, kan een team echter maar 5 × 3 = 15 punten halen, dus het beste team kan niet 20 punten hebben. Dus ook dit geval is niet mogelijk.

Het aantal wedstrijden en het aantal punten

Aan de hand van de twee voorbeelden die we bekeken hebben, is duidelijk dat het laatste team niet heel weinig, maar ook niet heel veel punten kan hebben. Tijd om dit wat algemener te bekijken. Als het laatste team $s$ punten heeft, dan hebben de andere teams $s + 2$, $s + 4$, $s + 6$, $s + 8$ en $s + 10$ punten. Noem het totaal aantal punten $T$. Er geldt dus $T = s + (s + 2) + ⋯ + (s + 10) = 6s+30$. We kunnen ook uitrekenen hoeveel wedstrijden er zijn gespeeld. Elk van de zes teams speelt vijf wedstrijden, want elk team speelt precies één keer tegen elk ander team. Omdat er bij elke wedstrijd twee teams spelen, is het totaal aantal wedstrijden dus $\frac12 × 6 × 5= 15$.

Als een wedstrijd in gelijkspel eindigt, levert dit in totaal $1 + 1 = 2$ punten op, anders wint er een team en verliest er een team en dit levert $3 + 0 = 3$ punten op. Als we het aantal wedstrijden dat in gelijkspel eindigt $g$ noemen, volgt dus dat het totaal aantal punten $T$ gelijk is aan $T = 2 × g + 3 × (15 – g) = 45 – g$. Voor het aantal wedstrijden dat in gelijkspel eindigt geldt $0 ≤ g ≤ 15$, dus $30 ≤ 45 – g ≤ 45$. Dus $30 ≤ T ≤ 45$. Daarom $30 ≤ 6s + 30 ≤ 45$ en omdat $s$ geheel is levert dit $s = 0, s = 1$ of $s = 2$. We hebben het geval $s = 0$ al gedaan, dus we hoeven nu alleen nog de gevallen $s = 1$ en $s = 2$ te bekijken.

 

Het laatste team heeft één punt

Op dit punt is het handig om nog een keer naar de opgave te kijken. We moeten bewijzen dat het team dat als vierde geëindigd is, precies twee wedstrijden heeft gewonnen. Dit team heeft dus minstens zes punten. Het team dat als laatste geëindigd is, heeft dan dus minstens twee punten. Dit geeft dus een hint dat we moeten bewijzen dat het niet mogelijk is dat het laatste team één punt heeft, dus dat het niet mogelijk is dat $s = 1$. We mogen natuurlijk niet hetgeen we moeten bewijzen gebruiken in de oplossing, maar de opgave kan dus wel een hint geven waar we naar toe moeten.

Merk op dat $s = 1$ betekent dat $T = 6 + 30 = 36$. Ook weten we dat $36 = 45 – g$, dus $g = 9$. Er zijn dus negen wedstrijden gelijkgespeeld en er zijn zes wedstrijden gewonnen. We kunnen nu kijken door welke teams er wedstrijden zijn gewonnen. Het beste team heeft $s + 10 = 11$ punten. Dit team heeft dus minstens drie wedstrijden gewonnen, want als ze twee wedstrijden of minder zouden hebben gewonnen, is hun score hoogstens $3 + 3 + 1 + 1 + 1 = 9$. Het tweede team heeft $9$ punten. Dit team heeft dus minstens twee wedstrijden gewonnen, want anders is hun score hoogstens $3 + 1 + 1 + 1 + 1 = 7$. Op dezelfde manier kan worden bewezen dat het derde team minstens één wedstrijd heeft gewonnen. De beste drie teams hebben dus samen minstens zes wedstrijden gewonnen. Maar er zijn maar zes wedstrijden in totaal gewonnen, dus de laatste drie teams hebben geen enkele wedstrijd gewonnen. Het laatste team heeft maar één punt, dus dit team heeft vier wedstrijden verloren. Hieruit volgt dat er vier teams zijn die van het laatste team hebben gewonnen. Maar we hebben net aangetoond dat er maar drie teams zijn die wedstrijden hebben gewonnen, dus we hebben een tegenspraak. Het is dus niet mogelijk dat het laatste team één punt heeft.

 

Het laatste team heeft twee punten

In het laatste geval dat we moeten bekijken, heeft het laatste team twee punten, dus $s = 2$. We weten dus dat het team dat vierde is geworden, zes punten heeft en we moeten bewijzen dat dit team twee wedstrijden gewonnen heeft.

Dit levert $T = 6s + 30 = 12 + 30 = 42$ en dus $g = 45 – T = 45 – 42 = 3$. Er zijn dus drie wedstrijden gelijkgespeeld en twaalf wedstrijden gewonnen. Het beste team heeft $12$ punten en heeft dus hoogstens $4$ wedstrijden gewonnen, anders zouden ze meer dan $12$ punten hebben. Op dezelfde manier hebben de teams met $10, 8, 6, 4$ en $2$ punten hoogstens $3, 2, 2, 1$ en $0$ wedstrijden gewonnen. Er zijn in totaal dus hoogstens $4 + 3 + 2 + 2 + 1 + 0 = 12$ wedstrijden gewonnen. Maar we weten dat er precies $12$ wedstrijden zijn gewonnen, dus dat betekent dat elk team het grootste aantal wedstrijden heeft gewonnen dat het qua aantal punten zou kunnen hebben gewonnen. Het vierde team heeft dus precies twee wedstrijden gewonnen en dat is wat we moesten bewijzen.

 

Terugblik

We kijken nog een keer naar de structuur van het bewijs. We hebben eerst bewezen dat het laatste team $0, 1$ of $2$ punten heeft. We hebben vervolgens laten zien dat de gevallen dat het laatste team $0$ punten of $1$ punt heeft niet mogelijk zijn. Het laatste team moet dus wel twee punten hebben en we bewezen dat dit betekent dat het vierde team twee wedstrijden gewonnen heeft. Het was heel nuttig om het aantal wedstrijden en het aantal punten uit te rekenen. Hierdoor konden we zien hoeveel wedstrijden er werden gewonnen en hoeveel er werden gelijkgespeeld. Eén van de gevallen hadden we al opgelost door kleine voorbeelden te bekijken. De andere gevallen hebben we opgelost door te kijken naar welke teams wedstrijden gewonnen hebben.

De opgave kan ook nog op een iets andere manier, door in het geval met één punt juist te kijken naar welke teams wedstrijden verliezen. Bij het geval met twee punten kun je kijken welke teams punten uit gelijkspel behalen. Deze oplossing kun je lezen in de officiële uitwerkingen, die je kunt vinden op de site van de Wiskunde Olympiade: wiskundeolympiade.nl.

Achteraf bleek deze opgave de best gemaakte opgave van de finale te zijn. De gemiddelde score was $5,7$ punten van de $10$ en ongeveer een derde van de deelnemers heeft deze opgave opgelost.