1
$\begingroup$

This question was originally posed on math.SE but seems to require research-level mathematics expertise:

Two players play each other in a match of games of chess where the match winner is the first to achieve either $m>0$ total game wins or $0<n<m$ game wins in a row. (There are no ties.) How many distinct possible sequences of game results exist as a function of $n$ and $m$?

For small values, one can write out the sequences (as in the linked question).

Clearly the shortest sequence of games is of length $n$ (of which there are two) and longest sequence of games is of length $2 m - 1$, but we seek the total number of distinct sequences.


First steps

Assume, without loss of generality, that the winning player is $A$ and the loser is $B$.

Let $0<k \leq 2m-1$ be the length of a sequence. If $k<n$ there is no match winner; we can ignore such cases.

There are, then, two ranges of interest:

  • $n \leq k < m$
  • $m \leq k \leq 2m -1$

In the first case, the only way $A$ wins the match is to win $n$ games in a row. Of course the last game (position $k$) $A$ wins, terminating the match. Thus the final $n$ games $A$ must win. That leaves $k-n$ preceding "other" slots. The last one of these must be won by $B$. Thus there are $k - n - 1$ remaining "unassigned" slots which can be won in any order so long as $A$ does not win $n$ in a row.

The number of ways this can be achieved is:

$$\sum\limits_{j=0}^{k-n-1} {k-n-1 \choose j}$$

but again, this over counts in certain cases because it includes cases in which $A$ wins $n$ consecutive games.

In the second case there are two categories of ways $A$ wins: by winning $m$ games or by winning $n$ in a row. In either of these cases, the last game (slot $k$) $A$ must win. If $A$ wins $m$ total games (on the $k$th game) then $A$ has won $m-1$ games in the $2m - 2$, and that means that $B$ has won the remaining $m-1$ games (but neither have won $n$ in a row).

The total number of ways this can be done is:

$$\sum\limits_{j=0}^{m-1} {2m - 2 \choose j}$$

but note that some of these cases may have $A$ win $n$ in a row. We must subtract those cases.

Another way to view part of the problem

Perhaps we can view this problem as a path through a lattice graph. Consider the number of sequences in which $A$ wins the match by winning $m$ games (and not by winning $n$ in a row). Each game won by $A$ is a lattice step to the right and each game won by $B$ is a step upward. Let's assume $A$ will be the winner. Thus the terminal nodes are those on the right-most column of the graph, $m$ steps horizontally.

Each path with be an alternating sequence of "streaks" of winning alternating by $A$ then $B$ then $A$... However, each of these streaks can be only of length $1, 2, \ldots, n-1$.

path through a lattice graph

So here we have $m=15$ and $n=4$. Each streak is of length less than $4$.

Each set of streaks of the winner $A$ represent an integer partition of $m$ restricted to elements $1, 2, \ldots, n-1$. (This is not the case for $B$, whose sum must be less than $m$ because $B$ loses.)

So the question can be restated as finding the number of distinct sequences of integer partitions of $m$, and for each such distinct sets of "streaks." Then, we find the number of integer partitions for $B$ that have the same number of streaks, or one greater or one less. Then we can alternate a streak for $A$ with a streak for $B$, and so on.

Counting this total number should give the number of sequences (paths) in which $A$ wins by reaching $m$ won games (but not having a streak of $n$).

Of course, this is not the full solution to the problem... but perhaps a casting that will help.

$\endgroup$
4
$\begingroup$

Let $g(i,j,k)$ be the number of sequences if the winner of the most recent game has won $i$ games, the opponent has won $j$ games, and the current win streak is $k$ games. Then $g$ satisfies the following recurrence: $$ g(i,j,k) = \begin{cases} 1 &\text{if $i=m$ or $k=n$},\\ g(i+1,j,k+1) + g(j+1,i,1) &\text{otherwise}. \end{cases} $$ The idea of the recurrence is to condition on the winner of the next game, as follows. If the most recent winner wins the next game, then both the win count $i$ and the consecutive win count $k$ increase by 1, and the opponent win count $j$ does not change, yielding $g(i+1,j,k+1)$. If instead the most recent winner loses the next game, then the win count $i$ does not change, the win count $j$ of the opponent increases by 1, the consecutive win count $k$ starts again at 1, and the opponent becomes the most recent winner, yielding $g(j+1,i,1)$.

We want to compute $g(0,0,0)/2$. For small $m$ and $n$, I get the following results: \begin{matrix} m\backslash n&1&2&3&4&5&6&7&8&9&10\\ 1&1\\ 2&1&3\\ 3&1&5&10\\ 4&1&7&26&35\\ 5&1&9&68&112&126\\ 6&1&11&174&362&442&462\\ 7&1&13&445&1176&1560&1689&1716\\ 8&1&15&1137&3827&5535&6207&6400&6435\\ 9&1&17&2908&12491&19722&22915&23992&24266&24310\\ 10&1&19&7445&40874&70503&84930&90323&91950&92324&92378 \end{matrix}

$\endgroup$
  • $\begingroup$ I may misread your notation by 1. For $(n,m) = (2,3)$ I get ten: $AA, BB, ABB, BAA, ABAA, BABB, ABABBk BABAA, ABABA, BABAB$, which your table has for $(3,3)$. Is there a slight convention misalignment? $\endgroup$ – David G. Stork Jan 26 at 5:35
  • $\begingroup$ $g(0,0,0)$ counts wins by either player. The table shows $g(0,0,0)/2$, which counts wins for player A. $\endgroup$ – Rob Pratt Jan 26 at 5:37
  • $\begingroup$ Ah... That's the source of the misalignment (+1). Thanks. If you could give just a bit more of the derivation of the recursion relation, I'll accept. $\endgroup$ – David G. Stork Jan 26 at 5:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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