The sum of the digits $1$ through $9$ is odd. They contribute to the parity of the digit sum of the result no matter which row they’re in. The digit sum of the result is odd. Thus there must be an even number of borrowings.
A column that causes borrowing must have a $7$, $8$ or $9$ in the bottom row, so we cannot have four borrowings.
On the other hand, if there were no borrowing at all, the possible pairs in a column would be $9-6-3$, $8-5-2$ and $7-4-1$, but we can use at most one from each of these three groups.
It follows that there are exactly two borrowings. Thus the difference between the digit sums of the rows must be $5\cdot3-2\cdot9=-3$, and since the sum of all digits is $\frac{9(9+1)}2=45$, the top row must sum to $21$ and the bottom row to $24$.
We need to have exactly two of $7$, $8$ and $9$ in the bottom row to cause the two borrowings.
It can’t be $7$ and $8$ because then $7$ would have to be subtracted from $1$ and $8$ from $2$, so the two borrowing columns would have to be the two lending columns.
If it were $8$ and $9$, that would leave a sum of $7$ for the bottom row, so that could be $3,4$ or $2,5$ or $1,6$. It can’t be $3,4$ because one of those needs to be $A_1$; it can’t be $2,5$ because $5$ would need to be subtracted from $8$ or $9$; and it can’t be $1,6$ because $6$ would need to be subtracted from $9$.
Thus $7$ and $9$ are in the bottom row. That leaves a sum of $8$ for the bottom row, which could be $3,5$ or $2,6$. But it can’t be $2,6$, again because $6$ would need to be subtracted from $9$.
Thus we have $3,5,7,9$ in the bottom row and $1,2,4,6,8$ in the top row. So $4$ must be $A_1$, $7$ must be subtracted from $1$, $9$ from $2$, $3$ from $6$ and $5$ from $8$. Thus the lenders must be $4$ and $1$, so the top row must start $412$. That leaves two possibilities for the order of the last two columns, so there are two solutions:
41286 41268
-7953 and -7935
----- -----
33333 33333
The solutions are confirmed by this Java code. (Full disclosure: I initially made a mistake in the proof and wrote the code to find it, so I knew the solution before I completed the proof.)
$$\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).$
Best Answer
Thanks to @C.C. idea about a connection with graph theory, I have first searched about graceful labeling of graphs and found A Dynamic Survey of Graph Labeling by Joseph A. Gallian, and there, on section 2.5, "Disconnected Graphs", a reference to Skolem Sequence, which is exactly what you are looking for.
The 1957 paper On certain distributions of integers in pairs with given differences by Th. Skolem proves that a Skolem sequence of length $2n$ exists if and only if $n \equiv 0,1 \pmod 4$.
Here I report the proof that no sequence can exist with $n \equiv 2,3 \pmod 4$. Proving that a sequence always exists for $n \equiv 0,1 \pmod 4$ is longer (see the article).
Let $(a_k,b_k)$, $k=1,\ldots,n$ be the chosen couples in $(1,2,\ldots,2n)$ with $a_k \lt b_k$. Therefore:
$$\sum_{k=1}^n (b_k-a_k) = \sum_{k=1}^n k = \frac{n(n+1)}{2}$$
and:
$$\sum_{k=1}^n (b_k+a_k) = \sum_{k=1}^{2n} k = n(2n+1)$$
adding the two equations yields:
$$\sum_{k=1}^n b_k = \frac{n(5n+3)}{4}$$
which is an integer only when $n \equiv 0,1 \pmod 4$.