Top 8?

Heb je een leuke wiskunde puzzel of een mooi vraagstuk gevonden en wil je die met ons delen? Post het hier.
Plaats reactie
ibraman
Nieuw lid
Nieuw lid
Berichten: 8
Lid geworden op: 06 mar 2008, 16:05

Top 8?

Bericht door ibraman » 30 okt 2008, 12:33

Hallo Allemaal.

Ik vroeg me af of iemand me kan helpen met het volgende probleem?

Ik doe geregeld mee aan toernooien. Deze toernooien hebben 5, 6 of 7 rondes afhankelijk van het aantal deelnemers.
Tot 2 deelnemers 1 ronde (gebeurt dus niet, minimum is 8 spelers)
Tot 4 deelnemers 2 rondes
Tot 8 – 3
Tot 16 – 4
Tot 32 – 5
Tot 64 – 6
Tot 128 – 7
Tot 256 – 8
Etc.

Er wordt na afloop van de reguliere rondes een top 8 toernooi gehouden; top 8 wil zeggen dat iedereen die qua punten in de hoogste rang zitten nrs 1 t/m 8 mag door.

Voor een gewonnen match krijg je 3 punten, voor een gelijkspel 1 en voor een verlies 0 punten.

Nu zoek ik een simpel formuletje waarmee ik kan uitrekenen hoeveel punten er nodig zijn of je in de top8 terecht komt.

Normaal mag je 1 verliezen en 1 gelijkspelen, maar soms is 2x verliezen ook genoeg en soms zelfs 2 verliezen en 1 gelijkspel volgens mij.

Dus stel er doen 78 mensen mee, is dan 2x verliezen goed genoeg om top 8 te halen?

En hoe zit het met random aantal spelers?

willemg2
Nieuw lid
Nieuw lid
Berichten: 22
Lid geworden op: 28 okt 2008, 18:16

Re: Top 8?

Bericht door willemg2 » 30 okt 2008, 18:58

Er kunnen toch nooit 78 spelers meedoen? in de tweede ronde heb je dan een oneven aantal spelers.
Volgens mij kunnen er allen 2^n spelers meedoen, waarbij n dus groter moet zijn dan 2.
(n = 3 => aantal spelers = 8, enzovoort) Alleen met die aantallen spelers kun je een toernooi houden, omdat er anders in een bepaalde ronde een oneven getal ontstaat.

(Bij 78 spelers is de kans op top8 dus 0, omdat dat toernooi niet gehouden wordt :D )

ibraman
Nieuw lid
Nieuw lid
Berichten: 8
Lid geworden op: 06 mar 2008, 16:05

Re: Top 8?

Bericht door ibraman » 31 okt 2008, 08:55

willemg2 schreef:Er kunnen toch nooit 78 spelers meedoen? in de tweede ronde heb je dan een oneven aantal spelers.
Volgens mij kunnen er allen 2^n spelers meedoen, waarbij n dus groter moet zijn dan 2.
(n = 3 => aantal spelers = 8, enzovoort) Alleen met die aantallen spelers kun je een toernooi houden, omdat er anders in een bepaalde ronde een oneven getal ontstaat.

(Bij 78 spelers is de kans op top8 dus 0, omdat dat toernooi niet gehouden wordt :D )
Er komen wel daadwerkelijk 78, 79, 63 spelers...
De rondes zijn swiss, dat wil zeggen geen eliminatie.

Na de 1e ronde worden iedereen met 3 punten tegenelkaar gepaired, mensen met 1 punt tegen elkaar en mensen met 0 punten tegenelkaar. Er kan ook voorkomen dat mensen met 3 punten (als er niet genoeg mensen zijn met 3 punten) tegen mensen met 1 punt of 0 punten wordt gepaired...

willemg2
Nieuw lid
Nieuw lid
Berichten: 22
Lid geworden op: 28 okt 2008, 18:16

Re: Top 8?

Bericht door willemg2 » 31 okt 2008, 16:31

OK, wist ik niet, sorry. Een universele oplossing kan ik helaas niet bedenken:S

arie
Moderator
Moderator
Berichten: 3922
Lid geworden op: 09 mei 2008, 09:19

Re: Top 8?

Bericht door arie » 02 nov 2008, 13:42

Dit is een leuk probleem!

Ik heb echter nog een aantal vragen en opmerkingen:

(1) Hoe gaat de wedstrijdleiding om met een oneven aantal deelnemers??
Als er bijvoorbeeld 13 spelers zijn, zou ieder 4 wedstrijden moeten spelen, waarvan de eerste om uit te maken of je in de top 8 komt. Dan blijft er altijd iemand over, of moet een ander twee wedstrijden spelen.

(2) Wanneer beland je precies in de top 8?
Volgens de beschrijving op basis van je puntentotaal, maar dit is niet voldoende.
Bijvoorbeeld: 10 spelers waarvan 5 de eerste wedstrijd winnen: er zijn dan 5 spelers met 3 punten en 5 met 0 punten. De 5 met 3 punten gaan door, maar welke 3 van de 5 met 0 punten komen in de top 8??
Ander voorbeeld: 60 spelers, 4 winnen 3 wedstrijden => 9 punten en 10 winnen 2 wedstrijden en spelen 1 keer gelijk => 7 punten. De 4 spelers met 9 punten gaan door, maar welke 4 van de 10 spelers met 7 punten gaan door naar de laatste 8??

(3) Hoe zit het precies met de pairing na elke ronde??
Een dergelijke pairing levert wel spannender wedstrijden, maar komt niet ten goede aan het eindresultaat van een toernooi.
Bijvoorbeeld: Stel de spelers hebben een absolute sterkte die we kunnen nummeren met N1, N2, N3, ..., vergelijkbaar met de (wereld-)ranglijst bij tennis of snooker of de ELO-rating bij schaken: nummer 1 (N1) is de beste, gevolgd door N2, gevolgd door N3 etc.
Nu wil je bij een toernooi dat de sterkste speler de grootste kans heeft op winst.
Bij een willekeurige (random) loting van wedstrijden lukt dit redelijk: als N1 3 wedstrijden moet spelen zal het gemiddelde van de 3 tegenstanders die hij/zij treft wsch ergens rond het gemiddelde van alle deelnemers aan het toernooi liggen.
Door geforceerde pairing in de voorrondes maak je de kans dat topspelers elkaar in die voorrondes al treffen veel groter (bijvoorbeeld de kans dat N1 in de voorrondes tegen N2, N3 en N4 moet spelen en hierdoor een grotere kans heeft voortijdig uitgeschakeld te worden).
Maar het kan allemaal nog veel erger:
Stel we hebben een toernooi met 64 deelnemers met werkelijke sterkte N1 t/m N64.
In ronde 1 spelen N1 t/m N32 tegen N33 t/m N64 (al dan niet bij toeval).
Nu winnen N1 t/m N32 alles volgens de verwachting: N1 t/m N32 krijgen allen 3 punten, N33 t/m N64 0 punten.
N1 t/m N32 moeten vervolgens door pairing onderling spelen:
In ronde 2 speelt bijvoorbeeld N1 tegen N2, N3 tegen N4, N5 tegen N6 etc
Deze zijn allen ongeveer even sterk en spelen allemaal gelijk: +1 punt ieder, totaal 4 punten.
In ronde 2 spelen ook N33 t/m N48 tegen N49 t/m N64, en winnen N33 t/m N48 =>
N33 t/m N48 hebben 3 punten, N49 t/m N64 0 punten.
Als we nu in ronde 3 weer pairen kunnen we krijgen:
(a) spelers met 4 punten:
N1 t/m N32: N1 treft N3, N2 treft N4, N5 treft N7, N6 treft N8 etc.
Hier zijn de sterktes weer ongeveer gelijk, alles gelijk spel levert +1 punt = 5 punten.
(b) spelers met 3 punten:
N33 t/m N48: N33 t/m N40 treffen N41 t/m N48, N33 t/m N40 winnen => +3 punten = 6 punten
(c) spelers met 0 punten:
N49 t/m N64: kunnen niet meer in de top 8 komen
De top 8 wordt zo dus gevormd door spelers met sterkte N33 t/m N40 met ieder 6 punten.
De spelers met sterkte N1 t/m N32 liggen er in de voorrondes al uit.
Nu is dit wel een extreem voorbeeld van gevolgen door te pairen, maar in algemeen geldt zeker dat door pairing de kans groter wordt dat sterkere spelers elkaar in de voorrondes treffen en daardoor voortijdig uitgeschakeld worden.



Dan nu je echte probleem: gegeven een aantal spelers, hoeveel punten moet je halen om er zeker van te zijn dat je bij de laatste 8 hoort.
Je wilt dan weten wat de maximale score is van de voorrondes, hoeveel personen die maximale score maximaal kunnen bereiken, vervolgens als er nog plaats over is in de top 8, wat dan de op 1 na hoogste score is, hoeveel mensen die kunnen bereiken etc.

Neem eerst het aantal spelers van 9 t/m 16:
er is dan 1 voorronde, de hoogst haalbare score = 3 punten.
- als het aantal deelnemers oneven is moeten we eerst probleem (1) van hierboven oplossen
- stel er zijn 16 deelnemers: er kunnen dan 8 winnen, en je moet dan dus winnen om zeker te zijn van een plaats in de top 8.
- stel er zijn 14 deelnemers:
--- er kunnen dan maximaal 7 personen 3 punten halen die naar de finale gaan, de 8e wordt gekozen uit de 7 verliezers (wie = probleem (2) hierboven)
--- stel er winnen er 6 (6x3 punten), de 7e partij speelt gelijk (2x1 punt): dan gaan de 6 winnaars door + de 2 spelers die gelijk gespeeld hebben: alle andere hebben 0 punten en gaan niet door.
--- stel er winnen er 5 (5x3 punten), de 6e en 7e partij weer gelijk (4x1 punt): 5 winnaars gaan door + 3 van de 4 gelijkspelers (wie = probleem (2))
etc.
ook nu moet je dus winnen om er zeker van te zijn dat je als gelijkspeler niet buiten de top 8 valt.
Dit geldt hier altijd: als iedereen de eerste wedstrijd gelijk speelt zijn er meer dan 8 deelnemers met 1 punt, er moeten dus gelijkspelers afvallen, en dus is gelijk spel niet voldoende.

Nu het aantal spelers van 17 t/m 32:
er zijn 2 voorrondes, hoogst haalbare score = 6 punten.
- 32 spelers:
--- 16 kunnen voorronde 1 winnen: 16x3 punten
------ bij pairing van deze 16 (zie probleem (3) hierboven) kunnen 8 hiervan tevens voorronde 2 winnen: 8 x 6 punten: je moet dus alle 2 je wedstrijden winnen om zeker te zijn van een plaats bij de laatste 8.
------ zonder pairing kunnen alle 16 winnaars van ronde 1 dan ook winnaar worden van ronde 2: er zijn dan dus 16 spelers met 6 punten (probleem (2) voor de wedstrijdleiding), winst van beide partijen is dus niet eens voldoende voor zekere plaatsing bij de laatste 8.
Kortom: je moet (ten minste) alles winnen om zeker te zijn van plaatsing bij de laatste 8.



Noot 1: dit is een ander probleem dan de vraag waarmee je mogelijk in de top 8 kan komen: je moet dan kijken naar de minimale scores van iedereen en van de groep: bij 32 spelers worden er 2 voorrondes gespeeld, de minimale prestatie wordt geleverd als iedereen gelijk speelt: 32 spelers met 2x1 = 2 punten.
Als jij dan als enige 1 wedstrijd wint heb je 1+3 = 4 punten, je tegenstander 1+0=1punt en alle andere spelers 1+1=2 punten.
Op deze manier bereik je als eerste met zekerheid de laatste 8: door 1x winst en 1x gelijk spel sta je nu immers als 1e genoteerd.

Noot 2: we hebben hier gekeken naar de situatie vooraf, als je kijkt naar de situatie tijdens het verloop van het toernooi wordt het nog wat ingewikkelder: bv bij 60 spelers zijn er 3 voorrondes, als je na 2 voorrondes al 6 punten hebt, en alle anderen hebben maximaal gelijk gespeeld, dus hebben maximaal 2 punten, dan ben je al door en hoef je niet eens je 3e voorronde te spelen.
In feite: heb je 6 punten en er zijn maximaal 7 anderen die maximaal 1 wedstrijd gewonnen hebben, dus maximaal 7 met 4 punten en de rest met maximaal 2 punten, ben je zeker van plaatsing.

Noot 3: deels hangt dit ook nog af van verdere selectie- en doorlatingscriteria in de regelementen van je sport. Dit is altijd een moeilijk punt samenhangend met probleem (3) hierboven waarvoor vele varianten oplossingen bestaan. Zo kent judo een herkansingssysteem: als je in een van de eerste rondes van de winnaar verliest zou je in sterkte best de nummer 2 van het toernooi kunnen zijn, en bij andere loting ook zilver hebben kunnen winnen. Daarom is er de extra regel: als je verliest van een tegenstander die daarna meerdere rondes verder komt, mag jij naar de herkansing.



Conclusie:
Om een lang verhaal kort te maken: gewoon alles winnen.

ibraman
Nieuw lid
Nieuw lid
Berichten: 8
Lid geworden op: 06 mar 2008, 16:05

Re: Top 8?

Bericht door ibraman » 03 nov 2008, 09:27

arie schreef:Dit is een leuk probleem!

Ik heb echter nog een aantal vragen en opmerkingen:

(1) Hoe gaat de wedstrijdleiding om met een oneven aantal deelnemers??
Als er bijvoorbeeld 13 spelers zijn, zou ieder 4 wedstrijden moeten spelen, waarvan de eerste om uit te maken of je in de top 8 komt. Dan blijft er altijd iemand over, of moet een ander twee wedstrijden spelen.

(2) Wanneer beland je precies in de top 8?
Volgens de beschrijving op basis van je puntentotaal, maar dit is niet voldoende.
Bijvoorbeeld: 10 spelers waarvan 5 de eerste wedstrijd winnen: er zijn dan 5 spelers met 3 punten en 5 met 0 punten. De 5 met 3 punten gaan door, maar welke 3 van de 5 met 0 punten komen in de top 8??
Ander voorbeeld: 60 spelers, 4 winnen 3 wedstrijden => 9 punten en 10 winnen 2 wedstrijden en spelen 1 keer gelijk => 7 punten. De 4 spelers met 9 punten gaan door, maar welke 4 van de 10 spelers met 7 punten gaan door naar de laatste 8??

(3) Hoe zit het precies met de pairing na elke ronde??
Een dergelijke pairing levert wel spannender wedstrijden, maar komt niet ten goede aan het eindresultaat van een toernooi.
Bijvoorbeeld: Stel de spelers hebben een absolute sterkte die we kunnen nummeren met N1, N2, N3, ..., vergelijkbaar met de (wereld-)ranglijst bij tennis of snooker of de ELO-rating bij schaken: nummer 1 (N1) is de beste, gevolgd door N2, gevolgd door N3 etc.
Nu wil je bij een toernooi dat de sterkste speler de grootste kans heeft op winst.
Bij een willekeurige (random) loting van wedstrijden lukt dit redelijk: als N1 3 wedstrijden moet spelen zal het gemiddelde van de 3 tegenstanders die hij/zij treft wsch ergens rond het gemiddelde van alle deelnemers aan het toernooi liggen.
Door geforceerde pairing in de voorrondes maak je de kans dat topspelers elkaar in die voorrondes al treffen veel groter (bijvoorbeeld de kans dat N1 in de voorrondes tegen N2, N3 en N4 moet spelen en hierdoor een grotere kans heeft voortijdig uitgeschakeld te worden).
Maar het kan allemaal nog veel erger:
Stel we hebben een toernooi met 64 deelnemers met werkelijke sterkte N1 t/m N64.
In ronde 1 spelen N1 t/m N32 tegen N33 t/m N64 (al dan niet bij toeval).
Nu winnen N1 t/m N32 alles volgens de verwachting: N1 t/m N32 krijgen allen 3 punten, N33 t/m N64 0 punten.
N1 t/m N32 moeten vervolgens door pairing onderling spelen:
In ronde 2 speelt bijvoorbeeld N1 tegen N2, N3 tegen N4, N5 tegen N6 etc
Deze zijn allen ongeveer even sterk en spelen allemaal gelijk: +1 punt ieder, totaal 4 punten.
In ronde 2 spelen ook N33 t/m N48 tegen N49 t/m N64, en winnen N33 t/m N48 =>
N33 t/m N48 hebben 3 punten, N49 t/m N64 0 punten.
Als we nu in ronde 3 weer pairen kunnen we krijgen:
(a) spelers met 4 punten:
N1 t/m N32: N1 treft N3, N2 treft N4, N5 treft N7, N6 treft N8 etc.
Hier zijn de sterktes weer ongeveer gelijk, alles gelijk spel levert +1 punt = 5 punten.
(b) spelers met 3 punten:
N33 t/m N48: N33 t/m N40 treffen N41 t/m N48, N33 t/m N40 winnen => +3 punten = 6 punten
(c) spelers met 0 punten:
N49 t/m N64: kunnen niet meer in de top 8 komen
De top 8 wordt zo dus gevormd door spelers met sterkte N33 t/m N40 met ieder 6 punten.
De spelers met sterkte N1 t/m N32 liggen er in de voorrondes al uit.
Nu is dit wel een extreem voorbeeld van gevolgen door te pairen, maar in algemeen geldt zeker dat door pairing de kans groter wordt dat sterkere spelers elkaar in de voorrondes treffen en daardoor voortijdig uitgeschakeld worden.



Dan nu je echte probleem: gegeven een aantal spelers, hoeveel punten moet je halen om er zeker van te zijn dat je bij de laatste 8 hoort.
Je wilt dan weten wat de maximale score is van de voorrondes, hoeveel personen die maximale score maximaal kunnen bereiken, vervolgens als er nog plaats over is in de top 8, wat dan de op 1 na hoogste score is, hoeveel mensen die kunnen bereiken etc.

Neem eerst het aantal spelers van 9 t/m 16:
er is dan 1 voorronde, de hoogst haalbare score = 3 punten.
- als het aantal deelnemers oneven is moeten we eerst probleem (1) van hierboven oplossen
- stel er zijn 16 deelnemers: er kunnen dan 8 winnen, en je moet dan dus winnen om zeker te zijn van een plaats in de top 8.
- stel er zijn 14 deelnemers:
--- er kunnen dan maximaal 7 personen 3 punten halen die naar de finale gaan, de 8e wordt gekozen uit de 7 verliezers (wie = probleem (2) hierboven)
--- stel er winnen er 6 (6x3 punten), de 7e partij speelt gelijk (2x1 punt): dan gaan de 6 winnaars door + de 2 spelers die gelijk gespeeld hebben: alle andere hebben 0 punten en gaan niet door.
--- stel er winnen er 5 (5x3 punten), de 6e en 7e partij weer gelijk (4x1 punt): 5 winnaars gaan door + 3 van de 4 gelijkspelers (wie = probleem (2))
etc.
ook nu moet je dus winnen om er zeker van te zijn dat je als gelijkspeler niet buiten de top 8 valt.
Dit geldt hier altijd: als iedereen de eerste wedstrijd gelijk speelt zijn er meer dan 8 deelnemers met 1 punt, er moeten dus gelijkspelers afvallen, en dus is gelijk spel niet voldoende.

Nu het aantal spelers van 17 t/m 32:
er zijn 2 voorrondes, hoogst haalbare score = 6 punten.
- 32 spelers:
--- 16 kunnen voorronde 1 winnen: 16x3 punten
------ bij pairing van deze 16 (zie probleem (3) hierboven) kunnen 8 hiervan tevens voorronde 2 winnen: 8 x 6 punten: je moet dus alle 2 je wedstrijden winnen om zeker te zijn van een plaats bij de laatste 8.
------ zonder pairing kunnen alle 16 winnaars van ronde 1 dan ook winnaar worden van ronde 2: er zijn dan dus 16 spelers met 6 punten (probleem (2) voor de wedstrijdleiding), winst van beide partijen is dus niet eens voldoende voor zekere plaatsing bij de laatste 8.
Kortom: je moet (ten minste) alles winnen om zeker te zijn van plaatsing bij de laatste 8.



Noot 1: dit is een ander probleem dan de vraag waarmee je mogelijk in de top 8 kan komen: je moet dan kijken naar de minimale scores van iedereen en van de groep: bij 32 spelers worden er 2 voorrondes gespeeld, de minimale prestatie wordt geleverd als iedereen gelijk speelt: 32 spelers met 2x1 = 2 punten.
Als jij dan als enige 1 wedstrijd wint heb je 1+3 = 4 punten, je tegenstander 1+0=1punt en alle andere spelers 1+1=2 punten.
Op deze manier bereik je als eerste met zekerheid de laatste 8: door 1x winst en 1x gelijk spel sta je nu immers als 1e genoteerd.

Noot 2: we hebben hier gekeken naar de situatie vooraf, als je kijkt naar de situatie tijdens het verloop van het toernooi wordt het nog wat ingewikkelder: bv bij 60 spelers zijn er 3 voorrondes, als je na 2 voorrondes al 6 punten hebt, en alle anderen hebben maximaal gelijk gespeeld, dus hebben maximaal 2 punten, dan ben je al door en hoef je niet eens je 3e voorronde te spelen.
In feite: heb je 6 punten en er zijn maximaal 7 anderen die maximaal 1 wedstrijd gewonnen hebben, dus maximaal 7 met 4 punten en de rest met maximaal 2 punten, ben je zeker van plaatsing.

Noot 3: deels hangt dit ook nog af van verdere selectie- en doorlatingscriteria in de regelementen van je sport. Dit is altijd een moeilijk punt samenhangend met probleem (3) hierboven waarvoor vele varianten oplossingen bestaan. Zo kent judo een herkansingssysteem: als je in een van de eerste rondes van de winnaar verliest zou je in sterkte best de nummer 2 van het toernooi kunnen zijn, en bij andere loting ook zilver hebben kunnen winnen. Daarom is er de extra regel: als je verliest van een tegenstander die daarna meerdere rondes verder komt, mag jij naar de herkansing.



Conclusie:
Om een lang verhaal kort te maken: gewoon alles winnen.
Flinke stuk text, maar hier even wat van je problemen opgelost:

(1) met 13 spelers word inderdaad 4 ronden gespeelt. Na afloop van de 4 ronden wordt er gekeken wie er het meeste punten heeft en de top 8 met de meeste punten gaat door naar de Top8.
Bij een gelijke hoeveelheid aan punten (dus #8 en #9 hebben beide 6 punten wordt er gekeken naar de weerstand, degene die tegen spelers heeft gespeeld die hoger zijn geeindigd heeft betere weerstand en staat hoger in de ranglijst.)

(2) hier wordt naar de weerstand gekeken, zoals ik hierboven heb beantwoord.
Dit hoeft in de berekening niet meegenomen te worden.
Zoals ik hierboven al zeg:
speler 1 heeft 10 punten en heeft gespeelt tegen #1, #3 en #6 op de ranglijst.
speler 2 heeft ook 10 punten en heeft gespeelt tegen #4, #8 en #9.
speler 1 heeft beter weerstand en eindigd hoger.

(3) de pairing is geheel random en iedereen is even goed. (het is een geluksspel waar ook beetje skill is gevraagd) op een normale toernooi komt ongeveer 80% met redelijke skills en 20% zonder skills spelen. Iedereen kan tegen iedereen gepaired worden.

Ook 1 ding wat niet vergeten moet worden. Er is geen eliminatie. Iedereen die mee doet speelt even veel rondes.
Dus als je ronde 1 verliest, maar de rest wint ga je toch naar de top8.
Jij denkt dat als er 14 mensen zijn er maar 1 ronde wordt gespeeld om te bepalen wie er naar de top 8 gaat. Dit is niet het geval. er worden bij 14 mensen zowiezo 4 ronden gespeelt en zijn er dus 12 punten te behalen voordat de top8 word bepaald.

Plaats reactie