[drbaskin]

"If you had 5,623 participants in a tournament, how many games would need to be played to determine the winner?" Let d = Log_2 N. Sum 2^(d-k) for k = 0 ... d

The a-ha solution to this puzzle is to realize that every participant but one has to lose exactly once. Each game has only one loser, so you need 5622 games.

Your method overestimates the number of games needed because you start counting at 0. (Think about the simple case where N=2.) Even if you started counting at 1, your method wouldn't in general give an exact answer (and would typically under- or over-estimate depending on whether you started counting at 1 or 0, respectively), but if you had a nice power of two (say, 2^d on the nose), then the sum from 1 to d of 2^(d-k) would give you exactly 2^d -1, which agrees with the a-ha answer.

[JoeAltmaier]

I don't get it - if there are 2 participants, you need N-1 == 2-1 == 1 game to determine the winner. The ah-ha answer still works.

[drbaskin]

The a-ha answer still works, but the orignal answer given has you sum 2^(d-k) from k =0 to d, so in this example would be 2^1 + 2^0, suggesting that you would need 3 games to determine the winner.

[aphyr]

Ah, yes, that is much nicer! Yeah, I did make an off-by-one error as well. Eh, constants. ;-)

[jtdowney]

Who said that the game they are playing has two participants with a winner and a loser.

[drbaskin]

Nobody, but it was implicit in the solution proffered by the post I replied to. If the game they are playing has 5623 participants with one winner and 5622 losers, you only need a single game!