0
$\begingroup$

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 2

3

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.

  • 0
    @Kou: the consistent thing would be the winner of a $2^n$ player tournament gets $\$100*(2^{n+1}-1)$2011-11-16
1

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?

  • 0
    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.2011-11-16