## Task 6A - 271246A

Alfred and Bernd share $n$ apples by deciding for each individual apple, in turn, through a random decision (e.g., flipping a coin) who will receive this apple.

Such a distribution process is called favorable for Alfred if and only if Alfred never has fewer apples in his possession than Bernd, not only at the end but throughout the entire process.

The probability $w(n)$ that a distribution process is favorable for Alfred is defined as the quotient obtained when the number of all favorable distribution processes for Alfred is divided by the number of all possible distribution processes.

(a) Determine $w(4)$.

(b) Determine $w(n)$ for any natural $n \geq 2$.
Each distribution process can be represented by an $n$-term sequence, where each term is either $A$ or $B$. Such a sequence is called a "$j$-sequence" if it contains exactly $j$ terms $A$. A sequence is called "favorable" if and only if it represents a favorable distribution process for Alfred.

For the largest integer $m \leq \frac{n}{2} \quad(*)$, the following statements hold:

(1) Every $j$-sequence with $j < m$ is unfavorable.

(2) The only $n$-sequence $(A A \ldots A)$ is favorable.

(3) For every $j$ with $m \leq j < n$, the number of all unfavorable $j$-sequences is equal to the number of all $(j+1)$-sequences.

This can be proven as follows:

For every unfavorable $j$-sequence $F$, there exists a smallest number $k \geq 1$ such that the $k$-th term is $B$, while among the preceding $k-1$ terms, there are as many terms $A$ as $B$.

Assign to the sequence $F$ the sequence $F'$ that is obtained from $F$ by replacing $A$ with $B$ and $B$ with $A$ in the first $k$ terms. For this assignment, the following holds:

I. The sequence $F'$ is always a $(j+1)$-sequence.

II. If two unfavorable $j$-sequences $F_1, F_2$ are different, then their assigned sequences $F_1', F_2'$ are also different.

III. Every $(j+1)$-sequence $G$ is the assigned sequence $G = F'$ of an unfavorable $j$-sequence $F$.

Since $j \geq m$, thus $j+1 \geq \frac{n}{2}$, $G$ contains more terms $A$ than $B$; therefore, there exists a smallest number $k \geq 1$ such that the $k$-th term is $A$, while among the preceding $k-1$ terms, there are as many terms $B$ as $A$.

Hence, the sequence that has the required properties (being an unfavorable $j$-sequence with $F' = G$) is the one that is obtained from $G$ by replacing $B$ with $A$ and $A$ with $B$ in the first $k$ terms.

With I., II., III., the claimed equality of counts is proven.

If the number of all $j$-sequences is denoted by $a_j$ and the number of all favorable $j$-sequences by $g_j$, then according to (1), (2), (3): The number of all favorable sequences is

$$
g_0 + \ldots + g_n = g_m + \ldots + g_{n-1} + g_n = (a_m - a_{m+1}) + \ldots + (a_{n-1} - a_n) + a_n = a_m
$$

The number $a_m$ of all $m$-sequences is known to be $a_m = \binom{n}{m}$, and the number of all $n$-term sequences to be considered is $2^n$. Therefore, we get
a) $w(4) = \binom{4}{2} : 2^4 = 6 : 16 = \frac{3}{8}$
b) $w(n) = \binom{n}{m} : 2^n$
with $m$ from $(*)$