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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Two players A and B plays a series of $2n$ games. Each game can result in either a loss or win for A. Find the total number of ways in which A can win this series of games. (All games are to be played)

I'm feeling a bit confused with this one. How to solve?

share|cite|improve this question
    
Does the series run until one of the sides reaches $n+1$ wins, or does it run all the way through (until all $2n$ games are done)? – barak manos Jan 14 at 14:46
    
I'm not sure @barakmanos I just wrote what my book says.But I find the former more practical (personally) – ZOZ Jan 14 at 14:47
    
If it runs until all games are done, then the answer is simply $\sum\limits_{k=n+1}^{2n}\binom{2n}{k}$. – barak manos Jan 14 at 14:48
    
Since it says all games are to be played, I think all 2n games are played. – SchrodingersCat Jan 14 at 14:48
    
@barakmanos: It says "all games are to be played" so that seems to mean "run all the way through". – Eli Rose Jan 14 at 14:48
up vote 6 down vote accepted

Since $2n$ games are going to be played each string of $2n$ games can be described by the games which A wins. Now A wins $k$ out of $2n$ games in $\dbinom{2n}{k}$ ways (order matters here when we count like this), so the total number of outcomes is equal to $$\sum_{k=0}^{2n}\dbinom{2n}{k}=(1+1)^{2n}=2^{2n}=4^n$$ by the Binomial Theorem. If A wins exactly $n$ games, then we have a tie. So there are $\dbinom{2n}{n}$ ties. Now due to symmetry, A wins exactly half of the rest of the strings, so the answer is $$\frac{\text{#total outcomes$-\#$ties}}{2}=\frac{4^n-\dbinom{2n}{n}}{2}=2^{2n-1}-\dbinom{2n-1}{n}$$


Plug in some values for $n$ to verify that this works. For example:

  1. $n=1$. Then there are $4^1$ outcomes: $ww, wl, lw, ll$ (where $w$ stands for a win of A and $l$ for a loss). In $1$ of those A wins.
  2. $n=2$. Then there are $4^2=16$ outcomes: $wwww, wwwl, wwlw, \dots$ and A wins in $$\frac{4^2-\dbinom{4}{2}}{2}=\frac{16-6}{2}=5$$ of them. B wins in other $5$ (by symmetry) and in $6$ outcomes we have a tie. You can check this by writing out all $16$ strings.
share|cite|improve this answer
    
Very nice.But will @Barack Manos's answer give the same result? – ZOZ Jan 14 at 15:07
    
@SanchayanDutta Yes. – Jimmy R. Jan 14 at 15:10
    
@SanchayanDutta: It must -- this is just a closed form for the sum barak manos gives. – Eli Rose Jan 14 at 15:10
1  
@barakmanos No, for $n=1$ it gives $1$ to me. But you are correct in the following sense: The sum as I have it (with result $4^n$) counts the outcomes $wl$ and $lw$ as different, so order matters (but I say that order does not matter). So, there are $4^1$ strings: $wl, ww, ll, lw$, but in the end $1$ way for A to win, so this comes out correctly. Note also, that $\sum_{k=0}^{2n}\dbinom{2n}{k}=\dbinom{2n}{n}+2\sum_{k=n+1}^{2n}\dbinom{2n}{k}$ so that your approach and mine give exactly the same result. – Jimmy R. Jan 14 at 15:21

If the series runs until all $2n$ games are played, then the answer is:

$$\sum\limits_{k=n+1}^{2n}\binom{2n}{k}$$


You simply need to sum up the number of ways in which A can win:

  • $n+1$ games out of $2n$ games
  • $n+2$ games out of $2n$ games
  • $\dots$
  • $2n$ games out of $2n$ games
share|cite|improve this answer
    
So that is $2^{2n}-2^{n}$ ? – ZOZ Jan 14 at 15:08
    
@SanchayanDutta: No, why would it be? – barak manos Jan 14 at 15:12
    
Can you tell me how to sum that series? I was trying to use $C(n, 0) + C(n, 1) + C(n, 2) + ... + C(n, n-1), + C(n, n) = 2^{n}$ and $C(2n, 0) + C(2n, 1) + C(2n, 2) + ... + C(2n, 2n-1), + C(2n, 2n) = 2^{2n}$ and subtracted the first from second..where am I going wrong? – ZOZ Jan 14 at 15:16
    
@SanchayanDutta: $C(n,\dots)$ is where you're going wrong. This term has nothing to do with $C(2n,\dots)$. It's like taking Pascal Triangle, summing up a row of $2n$ terms, then a row of $n$ terms, then subtracting one from the other. In the formula above, you need to sum up a row of $2n$ terms, and then subtract the first $n-1$ terms from the result. – barak manos Jan 14 at 15:17
    
Oh right...but how to sum that then? – ZOZ Jan 14 at 15:21

Since all games are to be played you want to count how many combinations of $0100 \ldots 0011$ there are (where $0 \to A$ loses and $1 \to A$ wins). The formal result is $$\sum\limits_{k=n+1}^{2n} (\text{combination where there are $k$ ones}) = \sum\limits_{k=n+1}^{2n}\binom{2n}{k}$$

share|cite|improve this answer

if you seek the number of combinations to arrange A and B (for which players who wins), the number of ways if all games are played is (2n)!

share|cite|improve this answer
    
You are supposed to determine in how many outcomes player A wins at least $n + 1$ of the $2n$ games. – N. F. Taussig Jan 14 at 14:54

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.