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.
To calculate number the of games, given the final score of the game
combinatoricsprobabilityprobability theory
Best Answer
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:
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}$
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).$