Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In a standard elimination tournament, a player wins $\$100k$ when she/he wins a match in the $k$th round. Develop and solve a recurrence relation for $a_n$, the total amount of money given away in a tournament with $n$ entrants, where $n$ is assumed to be a power of $2$.

I seem always to fail build recurrence relations... I hope someone could explain it to me in details.

share|improve this question
    
I presume that $n$ is a power of $2$, not $2n$, and edited the question suitably. –  Srivatsan Nov 16 '11 at 17:16

3 Answers 3

I assume you expect $n$ to be a power of $2$, not $2n$. Each tournament of $n$ is composed of two tournaments of $n/2$ plus one game worth $\$100\log_2(n)$. So if $D(n)$ is the distribution of a tournament of $n$ players, $D(n)=2D(n/2)+100\log_2(n)$. It would be easier to think in terms of $r=\log_2 n$, the number of rounds of the tournament. Using $E$ to avoid confusion, $E(r)=2E(r-1)+100\cdot r$

share|improve this answer
    
But the amount awarded for winning a game depends on the round. –  Gerry Myerson Nov 16 '11 at 5:41
    
+1 for the suggestion, but I think the problem is a little bit more complicated than that. –  Patrick Da Silva Nov 16 '11 at 5:44
    
@GerryMyerson: I missed the $k$ in the problem. Fixed. –  Ross Millikan Nov 16 '11 at 6:02
    
I find the notation very confusing (you talk of both $n$ as a power of $2$ and of $2^n$)... and the recurrence $D(n) = 2D(n/2) + 100n$ doesn't make sense; the last term should be $100r$ since it's the $r$th round. It should probably be $E(r) = 2E(r-1) + 100r$ and not what you have. –  ShreevatsaR Nov 16 '11 at 6:33
    
@ShreevatsaR: I agree. See what you think now. –  Ross Millikan Nov 16 '11 at 13:43

Here’s a more direct way to get the recurrence relation. Let $T(n)$ be the total given away when there are $2^n$ players. Suppose that we double the number of players, from $2^n$ to $2^{n+1}$. Let $P$ and $Q$ be the players who meet in the final round. Each of them is the winner of a tournament with $2^n$ players, namely, the sub-tournaments consisting of the two brackets of the whole tournament. These sub-tournaments started in round $1$, so each of them has paid out $T(n)$ dollars, for a total of $2T(n)$ dollars. All that remains is to figure out how much is paid to the winner of the final round. The first round eliminated half of the $2^{n+1}$ players, leaving $2^n$ still in the competition. The second round eliminated half of those, leaving $2^{n-1}$ still in the running. In general, each round eliminates half of the remaining contestants, so after $k$ rounds there must be $$\frac{2^{n+1}}{2^k}=2^{n+1-k}$$ contestants. In particular, after $n$ rounds there are $2^{n+1-n}=2$ contestants, so the last round is the $(n+1)$-st round and pays out $100(n+1)$ dollars. Thus, $$T(n+1)=2T(n)+100(n+1)\;.$$

While this is a more direct route to the recurrence, it isn’t necessarily an easier solution to find: playing with small cases leads pretty directly to Patrick’s more computational solution, which in turn also has the virtue of leading quite easily to a closed form for $T(n)$.

share|improve this answer

I think Ross's answer is the beginning of things but that he had it wrong. Let me explain.

You have $2^n$ players to begin with, hence $2^{n-1}$ matches for the first round. This gives us $2^{n-1}$ winners for the first round, hence $1 \times 100 \times 2^{n-1}$ dollars given away. Then $2^{n-1}$ players go to the second round, we have $2^{n-2}$ winners and they win $2 \times 100 \times 2^{n-2}$. We are left with $2^{n-2}$ players for the third round, $2^{n-3}$ winners, and they win $3 \times 100 \times 2^{n-3}$ dollars. It is easy to see that this keeps going on by induction on $k$, the round, and that the total amount of winnings at the $k^{\text{\th}}$ round will be $k \times 100 \times 2^{n-k}$ for $k = 1, \dots, n$. Thus $$ \text{Total}(n) = \sum_{k=1}^n \, (k \times 100 \times 2^{n-k}) = 2^n \times 100 \times \left( \sum_{k=1}^n \frac{k}{2^k} \right). $$ If you compute $\text{Total}(n+1)$ a little, you obtain $$ \begin{align} \text{Total}(n+1)= 2^{n+1} \times 100 \times \left( \sum_{k=1}^{n+1} \frac k{2^k} \right) \\ = 2^{n+1} \times 100 \times \left( \sum_{k=1}^{n} \frac k{2^k} + \frac{n+1}{2^{n+1}} \right) \\ = (n+1) \times 100 + 2 \times 2^n \times 100 \times \left( \sum_{k=1}^n \frac k{2^k} \right) \\ = (n+1) \times 100 + 2 \,\, \text{Total}(n) \\ \end{align} $$ Thus a recurrence formula for $T(n)$ would be $T(n+1) = (n+1)100 + 2T(n)$.

Hope that helps,

EDIT : You also have a more explicit formula for $T(n)$ by the following. Consider the geometric sum $$ \sum_{k=1}^n x^k = \frac{x^{n+1} - 1}{x-1}. $$ Thus $$ \begin{align} \sum_{k=1}^n kx^k &= x \left( \sum_{k=1}^n kx^{k-1} \right) \\ &= x \frac{d}{dx} \left( \sum_{k=1}^n x^k \right) \\ &= x \frac {d}{dx} \left( \frac{x^{n+1} - 1}{x-1} \right) \\ &= x \left( \frac{(n+1)x^n}{x-1} - \frac{x^{n+1} - 1}{(x-1)^2} \right) \\ &= \frac x{(x-1)^2} \left( (n+1)x^n(x-1) - x^{n+1} + 1 \right) \\ &= \frac x{(x-1)^2} \left( nx^{n+1} - (n+1) x^n + 1 \right). \end{align} $$ Let $x=1/2$ and you get $$ \sum_{k=1}^n \frac{k}{2^k} = 2 \left( \frac n{2^{n+1}} - \frac{(n+1)}{2^n} + 1 \right) = \frac{2^{n+1} - n -2}{2^n}. $$ This means that $$ T(n) = 2^n \times 100 \times \left( \frac{2^{n+1} - n - 2}{2^n} \right) = 100 (2^{n+1} - n - 2). $$

share|improve this answer
    
$T(n+1)$ has two tournaments of size $2^n$ so there needs to be a coefficient of $2$ on the $T(n)$. Between us we'll get it right. –  Ross Millikan Nov 16 '11 at 6:08
    
I think it's fine now. Uh yeah, forgot the two, that's a typo, thanks. –  Patrick Da Silva Nov 16 '11 at 6:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.