Q:

This problem is taken from the delightful book "Problems for Mathematicians, Young and Old" by Paul R. Halmos. Suppose that 681 tennis players want to play an elimination tournament. That means: they pair up, at random, for each round; if the number of players before the round begins is odd, one of them, chosen at random, sits out that round. The winners of each round, and the odd one who sat it out (if there was an odd one), play in the next round, till, finally, there is only one winner, the champion. What is the total number of matches to be played together, in all the rounds of the tournament

Accepted Solution

A:
Answer:680 gamesStep-by-step explanation:Suppose that 681 tennis players want to play an elimination tournament. 1st round:One of 681 players, chosen at random, sits out that round and 680 players play. There will be 340 winners plus one player which sits - 341 players for the next round and 340 games2nd round: There will be 170 winners plus one player which sits - 171 players for the next round and 170 games3rd round:There will be 85 winners plus one player which sits - 86 players for the next round and 85 games4th round:There will be 43 winners - 43 players for the next round and 43 games5th round:There will be 21 winners plus one player which sits - 22 players for the next round and 21 games6th round:There will be 11 winners Β - 11 players for the next round and 11 games7th round:There will be 5 winners plus one player which sits - 6 players for the next round and 5 games8th round:There will be 3 winners Β - 3 players for the next round and 3 games9th round:There will be 1 winner plus one player which sits - 2 players for the next round and 1 game10th round - final:1 champion and 1 game.In total,340 + 170 + 85 + 43 + 21 + 11 + 5 + 3 + 1 + 1 = 680 games