Wiskundemeisjes

Ionica & Jeanine
 
Slik Internetbureau Rotterdam Internetbureau Rotterdam



Categorieën

Archief

Schaakstelling


In Nieuws,Puzzels, door Ionica

Fokko van de Bult verdedigt komende donderdag in Amsterdam zijn proefschrift Hyperbolic Hypergeometric Functions. Stelling 8 van dat proefschrift lijkt verdacht veel op een leuke wiskundepuzzel.

Maarten schaakt

Stel dat de schaakkwaliteiten van een groep van n mensen volledig geordend zijn, in de zin dat als speler A beter is dan B hij altijd van B wint, en als B altijd van C wint, wint ook A altijd van C. Stel bovendien dat elke speler na 10 verloren wedstijden verloren te hebben (onafhankelijk van het aantal gewonnen wedstrijden) teleurgesteld naar huis gaat. Dan bestaat er een algoritme om indelingen te maken, alleen gebaseerd op uitkomsten van voorgaande wedstrijden, zodat met zekerheid de complete ordening in sterkte van deze groep spelers te bepalen is dan en slechts dan als n < 210.

Schaken Euwe Donner

Heeft een van jullie een idee hoe het algoritme de indelingen bepaalt?

Fokko waarschuwde ons dat dit niet echt een makkelijk probleem is. Het zou qua niveau een opgave op de Internationale Wiskunde Olympiade kunnen zijn. Fokko won zelf twee zilveren medailles op de internationale olympiade in 1997 en 1998 en traint al jaren de Nederlandse deelnemers.

9 reacties op “Schaakstelling”

  1. Maarten:

    Kleine correctie: Fokko verdedigt komende *donderdag* zijn proefschrift.

    Ik heb overigens geen idee hoe dit algoritme er uit zou moeten zien.

  2. Ionica:

    Stom van me, ik heb het verbeterd!

  3. Albert Hendriks:

    Ik heb 'em opgelost

  4. Ionica:

    Wow! Wil je je oplossing of een hint posten?

  5. Albert Hendriks:

    Gebruik merge sort:
    Je maakt rijtjes van spelers die gesorteerd zijn van goed naar slecht. Je begint met 2^10-1 rijtjes van lengte 1 (elke rijtje bestaat uit 1 speler en is dus al gesorteerd).
    Het idee is nu om in elke stap het aantal rijtjes te halveren en de lengte van elk rijtje te verdubbelen. Dit doe je door 2 gesorteerde rijtjes samen te voegen tot 1 grotere gesorteerde rij. Zodoende kost dit 10 stappen.
    In elk van die 10 stappen verliest elke speler maximaal 1 keer, wanneer je het samenvoegen van twee rijtjes alsvolgt doet: Neem van beide rijtjes de slechtste speler en laat die tegen elkaar spelen. De verliezer komt onderaan de grotere rij en wordt verwijderd uit zijn rijtje. Herhaal dit (een van de spelers is de winnaar van de vorige partij en de andere is de nieuwe onderste van het andere rijtje). De verliezer komt steeds op de onderste nog lege plek van de grotere rij.
    Als dit klopt dan moet de voorwaarde n

  6. Albert Hendriks:

    (mijn vorige post was afgeknipt)
    Als dit klopt dan moet de voorwaarde n

  7. Albert Hendriks:

    okay, de kleiner dan werkt niet :) wat ik wil zeggen is dat n volgens mij ook nog 1024 mag zijn, en niet maximaal 1023 zoals in de oorspronkelijke post staat.

  8. Ionica:

    @ Albert: Dit was precies de oplossing die Fokko in gedachten had. En het werkt inderdaad voor 1024, er moet in de vraag eigenlijk ook kleiner dan of gelijk staan

  9. Albert Hendriks:

    ah leuk :)

Plaats een reactie


Je kunt LaTeX gebruiken in je reactie.
Gelieve antwoorden op puzzels tussen [SPOILER] en [/SPOILER] te plaatsen.