# Problem on Divide-and-Conquer Relation

In a tennis tournament each player receives k hundreds of dollars where k is the number of people in the sub-tournament won by the player(the subsection of the tournament including the player, the player's victims, the victims of the player’s victims, and so on; a player who loses in the first round gets $100). If the tournament has n contestants, where n is a power of 2, find and solve a recurrence relation for the total prize money in the tournament. I got quite confused by this long problem, and fail to build the recurrence relation... - ## 2 Answers Hint: We assume there are$2^n$players so there are no byes. Each player who loses in the first round gets$\$100$, there are $2^{n-1}$ of them. Each player who loses in the second round gets $\$300$, there are$2^{n-2}$of them. Each player who loses in the third round gets$\$700=100(2^3-1)$. Sum over the rounds and worry about what happens at the end.

-
Although you say "Each player who loses in the first round gets nothing", the problem says "a player who loses in the first round gets $100". – jwpat7 Nov 15 '11 at 5:16 @jwpat7: I read it that it contradicts the statement that "k hundreds of dollars where k is the number of people in the sub-tournament won by the player(the subsection of the tournament including the player, the player's victims, the victims of the player’s victims, and so on", but another read confirms your statement. It shifts the indices of the sums by 1, I'll fix. Thanks much. – Ross Millikan Nov 15 '11 at 5:27 @RossMillikan I was wondering why "Each player who loses in the second round gets$300"... – Kou Nov 16 '11 at 4:37
@Kou: they beat one player in the first round and lost in the second round, so they get \$100 for the one they beat, themselves, and the one they lost to. My original answer said they got \$100 for the one they beat, which I think is a more reasonable approach but contradicts the question as asked. – Ross Millikan Nov 16 '11 at 4:42
@RossMillikan Oh, I see. But how about the final winner? I fail to figure it out... – Kou Nov 16 '11 at 4:49

What's the total prize money when $n=2$? What about when $n=4$? What about when $n=8$? Do you see a pattern going from one answer to the next? Can you make a recurrence relation out of that pattern? Can you solve it?

-
Actually I was confused even when n=4... – Kou Nov 16 '11 at 4:38
So, let's look at $n=4$. Players $a,b,c,d$. Round 1, $a$ beats $b$, $c$ beats $d$. This is an elimination tournament (right?) so $b,d$ go home with 100 each. Second (and last) round, $a$ beats $c$. The subtournament for $c$ is $c,d$, so $c$ gets 200; the subtournament for $a$ is $a,b,c,d$ so $a$ gets 400. The total payout is 800. – Gerry Myerson Nov 16 '11 at 6:05