To calculate number the of games, given the final score of the game

Suppose you have a game (a game is defined as a set of 275 matches). In each match Player 1 gets a point if he wins and Player 2 gets 10 points if he wins. Let the final score of the game be $267:80$ (Player 1 score: Player 2 score). So, Player 1 won 267 times and Player 2 only 8 times. The first question is: what is the possible number of games that could have ended with a given final score? The second is: what is the number of games ending with a given final score where Player 1 was leading throughout the game (except for the very beginning, where the score is $0:0$)? And in the end you can therefore calculate the probability of Player 1 leading throughout the game, that ended in a given score under the assumption that all sequences of games are equally likely. The question is from the Russian olympiad "Я профессионал"("I am a pro") for university students, in which I participated this year, but was unable to solve this problem, which I memorized and translated into English. The answer to the first question is $\binom{275}{8}$ as pointed out by the comments and for the second question we consider the expression $$\binom{275}{8} - \left|\bigcup_{k=1}^{8}{A_k}\right|$$ Where $A_k$ is the event of Player 2 winning at least $k$ times in the first $10k$ matches. $$\binom{275}{8} - \left|\bigcup_{k=1}^{8}{A_k}\right|=\binom{275}{8} -\left( \sum_{k=1}^{8}{|A_k|}-\sum_{1\leq i<j\leq8}{|A_i\cap A_j|}+\sum_{1\leq i<j<k\leq8}{|A_i\cap A_j\cap A_k|}-\dots+(-1)^{7}|A_1\cap\dots\cap A_8|\right).$$ So,$\sum_{k=1}^{8}{|A_k|}=\sum_{k=1}^{8}{\sum_{i=1}^{8}{\binom{10k}{i}}}=47038748632$. Then $$\sum_{1\leq i<j\leq8}{|A_i\cap A_j|}=|A_1\cap A_2|+\dots+|A_1\cap A_8|+|A_2\cap A_3|+\dots+ |A_2\cap A_8|+|A_3\cap A_4|+\dots |A_3\cap A_8|+|A_4\cap A_5|+\dots+|A_4\cap A_8|+|A_5\cap A_6|+\dots+|A_5\cap A_8|+|A_6\cap A_7|+\dots+|A_6\cap A_8|+|A_7\cap A_8|$$ If we take for instance $|A_1\cap A_2|$, then I guess $|A_1\cap A_2|=|A_1|^2=\left(\sum_{i=1}^{8}{\binom{10}{i}}\right)^2=1012^2$. So, $|A_1\cap A_3|=|A_1||A_2|=1012\cdot 263949$. My logic for $|A_1\cap A_3|$ is that we need to have both at least 1 win in the 1st 10 and at least 3 in the 1st 30 matches, but that is the same as saying at least 1 win in the 1st 10 and at least 2 in the last 20. However, I am not sure about my reasoning, can anyone point out how to calculate these $|A_i\cap A_j|$ terms correctly in this case? The same question goes for $|A_i\cap A_j\cap A_k|$ terms. If I figure out how to do them, the second question reduces to computations and the overall problem would be solved. Any help is much appreciated.

Solution 1:

$$\binom{275}{8} - \left|\bigcup_{k=1}^{8}{A_k}\right|$$ Where $A_k$ is the event of Player 2 winning at least $k$ times in the first $10k$ matches.

In the comments, I suggested using Inclusion-Exclusion, which is represented by the above excerpt from the original posting. However, I found the enumeration to be so ugly that I will instead use a direct approach.

For $k \in \{1,2,\cdots,8\}$, let $x_k$ denote the exact number of player-2 wins that occur in games $[10k - 9]$ through $[10k]$ inclusive. In order for the 2nd player to be even or ahead at some point, one of the following constraints must be satisfied:

• $x_1 \geq 1.$
• $x_1 + x_2 \geq 2.$
• $x_1 + x_2 + x_3 \geq 3.$
• $\cdots$
• $x_1 + x_2 + \cdots + x_8 \geq 8.$

This means that in order for the first player to always be ahead, all of the following constraints must be satisfied:

$\textbf{Set of 8 Constraints}$

• $x_1 < 1.$
• $x_1 + x_2 < 2.$
• $x_1 + x_2 + x_3 < 3.$
• $\cdots$
• $x_1 + x_2 + \cdots + x_8 < 8.$

So, how can the above analysis be used to enumerate the number of pertinent distributions?

First, you must obtain a complete list of all ordered $8$-tuples that satisfy the $8$ constraints above. Then, for each such $8$-tuple, the enumeration is

$$\binom{10}{x_1} \times \binom{10}{x_2} \times \cdots \times \binom{10}{x_8} \times \binom{275 - 80}{8 - [x_1 + x_2 + \cdots + x_8]}. \tag1 $$

Suppose that the number of distributions where player-1 is always ahead is $S$. Then, in order to compute $S$, you must use the formula in (1) above to attach a number to each $8$-tuple that satisfies all of the $8$ constraints.

Then, $S$ equals the sum of all of these attached numbers. Then, as indicated in the original posting, the probability of player-1 always being ahead is

$$\frac{S}{\binom{275}{8}}.$$

I know of no easy way of identifying all of the satisfying $8$-tuples, except by writing a simple computer program. Such a computer program could then easily apply the formula in (1) above to each of the satisfying $8$-tuples. This implies that such a computer program can routinely compute $S$.

For what it's worth, the manual enumeration of each satisfying $8$-tuple will look like:

$(0,0,0,0,0,0,0,0)$
$(0,0,0,0,0,0,0,1)$
$(0,0,0,0,0,0,0,2)$
$\cdots$
$(0,0,0,0,0,0,0,7)$

$(0,0,0,0,0,0,1,0)$
$(0,0,0,0,0,0,1,1)$
$(0,0,0,0,0,0,1,2)$
$\cdots$
$(0,0,0,0,0,0,1,6)$

$(0,0,0,0,0,0,2,0)$
$(0,0,0,0,0,0,2,1)$
$\cdots$
$(0,0,0,0,0,0,2,5).$

$\cdots$
$(0,0,0,0,0,0,6,0).$
$(0,0,0,0,0,0,6,1).$

$(0,0,0,0,0,1,0,0)$
$\cdots$
$(0,1,1,1,1,1,1,1).$