Re:The most ridiculous job interview questions
by JoeAltmaier on Wednesday April 06, 2011 @10:20AM
(#2415149)
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.
Re:The most ridiculous job interview questions
by drbaskin on Wednesday April 06, 2011 @10:47AM
(#2415257)
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.
Re:The most ridiculous job interview questions
by aphyr on Wednesday April 06, 2011 @01:26PM
(#2415989)
Ah, yes, that is much nicer! Yeah, I did make an off-by-one error as well. Eh, constants. ;-)
Re:The most ridiculous job interview questions
by jtdowney on Wednesday April 06, 2011 @05:37AM
(#2414479)
Who said that the game they are playing has two participants with a winner and a loser.
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.