1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Knock out tournament to find first places

  1. Apr 11, 2010 #1
    Does anyone know a system how to schedule a tournament in order to find the top k players?

    In each game two players play and one comes out as a winner. I assume that each player has a definite strength and always the stronger player wins. Each day each player can play one game and all players can play simultaneously.
    I'd like to find a system where in the end tells me the top ranked players with their order.

    A simple knock out tournament gives the top player.
    A double elimination tournament can tell places 1-4, but already some care in the pairing has to be taken to ensure the knowledge of 4th place?!
    Is there a general scheduling system?

    I'd like to make it mathematically correct, rather than some common systems which give incorrect 4th places.
     
  2. jcsd
  3. Apr 11, 2010 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    I think this is a very hard problem, in general. If you have such a schedule, it's trivial to find Sloane's A036604, the minimum number of games that need to be played in the worst case: 0, 1, 3, 5, 7, 10, 13, 16, 19, 22, 26, 30, 34, 38, ....

    If you're willing to accept a higher number of games than the theoretical minimum, merge sort seems pretty good. In particular, for up to 14 teams/elements, it's optimal. See Sloane's A001768.
     
  4. Apr 11, 2010 #3
    I tried estimating the number of games with some logic. which basically boils down to using log_2 :)
    I know merge sort from computer algorithms, but it sorts all the elements? I only need the top k. Maybe places 1-4 or 1-6 or whatever.
    Also for my purposes I only want to have the minimum numbers of days so it's OK if some superfluous games are played simultaneously one day if that makes the system easier.

    Interesting things about merge sort and 14 teams. Thanks :)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Knock out tournament to find first places
Loading...