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.

  • 1
    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".2011-11-15
  • 0
    @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.2011-11-15
  • 0
    @RossMillikan I was wondering why "Each player who loses in the second round gets $300"...2011-11-16
  • 0
    @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.2011-11-16
  • 0
    @RossMillikan Oh, I see. But how about the final winner? I fail to figure it out...2011-11-16
  • 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
    Actually I was confused even when n=4...2011-11-16
  • 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