Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Maths: Gladiatorial league

  1. Sep 27, 2012 #1
    Say there are N gladiators, and I want to find the champion among them. The method by which this is done is a series of elimination rounds, which are similar to but not quite like the methods used in many modern sports events:

    Each gladiator is given a number from 1 to N. Each gladiator then fights the n gladiators with numbers immediately lower than their own and the n gladiators with numbers immediately higher than their own, where n is some constant much smaller than N. For example, if n=2, then gladiator #50 fights gladiators #49, #48, #51, and #52 in the first round.

    Only those who win all of their fights advance to the next round, and the process repeats. To continue the example, assuming that our #50 won all four fights, then all of their opponents were necessarily eliminated because they lost at least one of their fights, namely the one with #50. So, in the second round, #50's closest possible opponents would be #47, #44, #53, and #56. Then again, it's possible that they are already the "last man standing", because nobody else managed to win all of their four fights.

    I haven't decided what happens "at the edges", i.e. who #1 fights in the first round, other than #2 and #3, if anyone. For practical reasons, they can't fight #N-1 and #N, which would of course be the tidiest solution. Let's treat that point as negligible, for now.

    It's easy to calculate how many rounds this championship will take at least - one, see above. It's almost as easy to calculate how many rounds it will take at most. However, how many rounds will it take typically, as a function of N and n?
  2. jcsd
  3. Sep 27, 2012 #2
    What happens if nobody wins all 4 his matches??
  4. Sep 27, 2012 #3


    User Avatar
    Science Advisor

    Doesn't sound like much of a Gladiator to me...
  5. Sep 27, 2012 #4
    I thought the matches are to the death.

    I am Spartacus!
  6. Sep 27, 2012 #5


    User Avatar
    Science Advisor

    Last edited by a moderator: Sep 25, 2014
  7. Sep 27, 2012 #6
    Anyway, I guess that this problem can be solved by making it in some kind of Markov chain. I'll try to find the solution if I'm bored.
  8. Sep 28, 2012 #7
    One can only become The Champion if one is undefeated. Thus, if nobody whatsoever makes it to the second round, there is no champion. Baaad omen, presumably.

    The weapons used are such that fights are typically to incapacitation rather than death, and killing one's opponent is frowned upon - as a sign of a lack of finesse, if nothing else. Accidental deaths aren't exactly infrequent occurrences either, though.

    micromass, if you could just outline the approach, I can probably take it from there. Mainly, my problem is that I have no real handle on how to estimate the chances of someone winning all 2n of their fights in a given round if they are better, in some objective sense, than all of their opponents. Somewhere between 1 and (1/2)^(2n), obviously, but that's not much help.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook