- #1

- 103

- 1

## Main Question or Discussion Point

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

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

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?