# Combinatorics of a tournament where one wins by taking either three games in a row or four in total

Two teams play each other repeatedly until either one of them wins three games in a row or one of them wins a total of four games. What are all the ways in which the tournament can be played? What is the probability that six games are needed to determine a winner?

### Progress

I've listed all the possibilities, but I'm afraid I might be missing a few or repeating some because I just did this by hand. I'm trying to figure out how to do this mathematically. I know that there are $$2^7$$ total possibilities, not including repeats. For example, BBBBBBB and BBBRRRR are the same because there would be three games, BBB. The remaining $$4$$ games would not matter since the tournament would have ended.

• There's a symmetry to this problem. It's easier to find how many ways one team can win in exactly 3, ... , 6 , (Max # of games possible) as the other team can way in the same exact ways. What have you worked on so far btw? This sounds like a homework problem.
– user64878
Sep 19 '14 at 4:58
• I've listed all the possibilities, but I'm afraid I might be missing a few or repeating some because I just did this by hand. I'm trying to figure out how to do this mathematically. I know that there are 2^7 total possibilities, not including repeats. For example, BBBBBBB and BBBRRRR are the same because there would be three games, BBB. The remaining 4 games would not matter since the tournament would have ended. You're right that I should do this in the opposite direction, because it would be easier, but I'm not sure how to go about it.
– nrc
Sep 19 '14 at 6:10
• @ why are saying $2^7$, the total possibilities should be $2^6$ is it not? Sep 19 '14 at 6:31
• It would be 2^7 because there can be 7 games with 7 slots and 2 choices in each. For example, RBRBRBR is a valid tournament with 7 games, R winning the tournament. I use R and B to denote different teams, by the way. Sorry I didn't clarify that in my previous post.
– nrc
Sep 19 '14 at 6:41
• Do we have to assume it is a 7 game series? Sep 19 '14 at 6:49

Keep track of each player's "state" after each game with two numbers. Let $r_i$ be the length of player $i$'s current run of wins, and let $g_i$ be player $i$'s number of games won. Let the state of the match be $(r_1,g_1,r_2,g_2)$. Initially, the match is in state $(0,0,0,0)$.

Let $w(a,b,c,d)$ be the generating function for the probability that a match that has reached state $(a,b,c,d)$ ends after a total of $i$ games. In other words, let $w(a,b,c,d)=\sum_i p_i x^i$, where $p_i$ is the probability that a match that has reached state $(a,b,c,d)$ ends after exactly $i$ games. Note that if $a=3$, $b=4$, $c=3$, or $d=4$, the match is over and took exactly $b+d$ games. In terms of the generating function, this means that $w(a,b,c,d)=x^{b+d}$.

Now suppose the state of a particular match is $(a,b,c,d)$. If player 1 wins the next game, the state moves from $(a,b,c,d)$ to $(a+1,b+1,0,d)$. If player 2 wins the next game, the state moves from $(a,b,c,d)$ to $(0,b,c+1,d+1)$.

If $p$ is the probability of player 1 winning a single game, the state of an ongoing match moves from state $(a,b,c,d)$ to either state $w(a+1,b+1,0,d)$ (with probability $p$) or state (with probability $1-p$). This gives a recurrence for the generating function. $w(a,b,c,d) = p w(a+1,b+1,0,d) + (1-p)w(0,b,c+1,d+1)$.

The generating function for the match-length probabilities of a fresh match is $w(0,0,0,0)$.

The recurrence and initial conditions fully characterize the generating function $w$.

• $w(a,b,c,d)=x^{b+d}$ if $a=3$, $b=4$, $c=3$, or $d=4$
• $w(a,b,c,d) = pw(a+1,b+1,0,d) + (1-p)w(0,b,c+1,d+1)$

$w(0,0,0,0)$ can be worked out by hand, but it's much easier to enlist the help of Mathematica or a similar tool.

$w(0,0,0,0)=\\(1-3 p+3 p^2) x^3+(p-3 p^2+4 p^3-2 p^4) x^4+(2 p-7 p^2+10 p^3-5 p^4) x^5\\+(7 p^2-28 p^3+49 p^4-42 p^5+14 p^6) x^6+(14 p^3-42 p^4+42 p^5-14 p^6) x^7$

If $p=\frac{1}{2}$, $w(0,0,0,0)=\frac{1}{4}x^3+\frac{1}{8}x^4+\frac{3 }{16}x^5+\frac{7 }{32}x^6+\frac{7}{32} x^7$.

The answer to many questions about this game can be deduced from $w$. For example, the probability that the match takes exactly $6$ games is the coefficient of $x^6$, $7 p^2-28 p^3+49 p^4-42 p^5+14$, which equals the value satish found, $7(p^4(1-p)^2 +p^2(1-p)^4)$.

If you want to answer questions about a particular player, you can use two variables in the generating function. Let the coefficient of $x^i$ represent the probability that player 1 wins and the match takes exactly $i$ games, and let the coefficient of $y^i$ represent the probability that player 2 wins and the match takes exactly $i$ games. This changes two of the initial condition values to $y^{b+d}$, but the recurrence is the same.

The number of ways the tournament could be played such that the winner is declared on the basis of either one wins three games in a row or one of them wins four games total.

Let A and B be the two teams that play each other repeatedly. The problem could be approached with one of the criteria evaluated first (three games in a row) and then relax the problem to allow for the second criterion to come in while at the same time maintaining that the other team does not win either based on the same rules and working backwards starting from the sixth game. Let p be the probability that A wins the game and (1-p) be the probability that B wins.

1) _ _ _ A A A.

In this case, A cannot be in the four position because, if it is then A would have won on the 5th game. So B is the only choice.

_ _ B A A A. Two B's or two A's are not allowed because, if it is then B could have won on 2B's and A could have won on the fifth game with 2A's.

Thus there can be only one A and one B permuted in the first two places. Thus there could only be

a) A B B A A A -

b) B A B A A A -

Now relax the first criterion and let the second criterion of total of four games could declare the winner. This can be further split into two cases which are

2) _ _ _ _ A A

3) _ _ _ _ _ A

In the second case, allow B to win in the fourth games because A in the fourth position is already covered which then reduces the case to be

2) _ _ _ B A A.

Now , there can only be 2 A's and 1 B occupying the first thee positions, because

3A's will make the A winner in 3 games, 3 B will make B the winner in three games, 2 B and 1 A will either make B a winner in the 4th game or there are not winners because for A to win you need four games.

c) A A B B A A

d) A B A B A A

e) B A A B A A

Now let us move on to the third case which is

3) _ _ _ _ _ A, In a similar argument that was made earlier that A occupying the fifth position would replicate 2nd Case, thus let B occupy the fifth position

3) _ _ _ _ B A. There are 16 ways to fill the first four positions. You can safely eliminate 4A's(1), 4B's(1), 3'B's & 1A's(4), 2B's and 2'A(6), for the reasons, either A or B wins prematurely or none of them are a clear winner. What is left is 3A's and 1B.

A A A B B A is a premature win.

B A A A B A is a premature win.

So you can eliminate these. So what is left are the two possibilities.

f) A A B A B A

g) A B A A B A

To summarize the possibilities of A to win

a) A B B A A A

b) B A B A A A

c) A A B B A A

d) A B A B A A

e) B A A B A A

f) A A B A B A

g) A B A A B A

Thus there are 7 possibilities for A to win. By symmetry, there are 7 possibilities for B to win. Thus there are 14 possibilities that either one of them will win under the basis that there are six games needed to find the winner.

The probability then is $7\left(p^4(1-p)^2 +p^2(1-p)^4\right)$