One of my favorites (that I was asked, and did not get quite right, but I was still hired):
In a single-elimination sports tournament with 16 teams, how many games do you need to play to have a winner? (Hint: 8+4+2+1=15. This is easy enough to brute-force in your head).
Okay, how many in a tournament with 1000 teams? How about 8674?
How do you calculate it?
...ANSWER BELOW...
You can do it by iteration, you can try to derive a formula...
Or, you can realize that:
- The tournament is over when 1 team remains (the winner)
- Each match eliminates 1 team
- Therefore, the number of required matches is (NumberOfInitialTeams - 1).
As for the hand-wringing over non-power-of-2 numbers of initial teams, please read the following:
http://en.wikipedia.org/wiki/Bye_%28sports%29
"A bye, in sports and other competitive activities, most commonly refers to the practice of allowing a player or team to advance to the next round of a playoff tournament without playing. This is generally the result of having a number of entrants in the competition that is not a power of two (i.e., not 4, 8, 16, 32, etc.); any such tournament must eventually through elimination arrive at an odd number of participants at some point, thus necessitating the bye. In large tournaments, sometimes the best-ranked players or teams get a bye in the first round(s), to reward them with less risk of elimination, as well as on the basis (particularly in seeded tournaments) that they would be most likely to eliminate the worst seeds anyway. Byes can be applied equally to single-person competitions and team sports, and well as to single-game eliminations and best-of series eliminiations."