XXXIV OM - II - Problem 6

For a given number $ n $, let $ p_n $ denote the probability that when a pair of integers $ k, m $ satisfying the conditions $ 0 \leq k \leq m \leq 2^n $ is chosen at random (each pair is equally likely), the number $ \binom{m}{k} $ is even. Calculate $ \lim_{n\to \infty} p_n $.
om34_2r_img_10.jpg
The diagram in Figure 10 shows Pascal's triangle written modulo $2$, meaning it has zeros and ones in the places where the usual Pascal's triangle has even and odd numbers, respectively. Just like in the usual Pascal's triangle, each element here is the sum of the elements directly above it, according to the addition table modulo 2: $0+0=0$, $0+1=1$, $1+0=1$, $1+1 = 0$. The drawn horizontal lines divide this triangle into layers:

- layer $W_0$ consisting of row number $0$,
- layer $W_1$ consisting of row number $1$,
- layer $W_2$ consisting of rows number $2$ and $3$,
- layer $W_3$ consisting of rows number $4$, $5$, $6$, $7$,
- $\ldots$
- layer $W_j$ consisting of rows with numbers from $2^{j-1}$ to $2^j-1$
- $\ldots$

We will prove by induction that in any layer $W_j$ there are two disjoint triangles, each identical to the triangle formed by the layers $W_0, W_1, \ldots, W_{j-1}$, and that these two triangles are separated by an inverted triangle composed entirely of zeros; the top row of the layer consists of extreme ones and zeros, and the bottom row of the layer consists of all ones.
For $j = 1, 2, 3$, this is visible from the diagrams (the diagonal lines define the division into the triangles mentioned). Assume the above relationships are true for some $j$ and consider the layer $W_{j+1}$. By the induction hypothesis, the last row of layer $W_j$ has the form $111\ldots 111$, and thus, according to the addition rule given above, the first row of layer $W_{j+1}$ has the form $100\ldots 001$. The extreme ones of this row give rise to two new copies of Pascal's triangle, and between them are zeros. Layer $W_{j+1}$ has as many rows as the layers $W_0, W_1, \ldots, W_j$ taken together, so at the base of each of these two triangles at the bottom of layer $W_{j+1}$ will be the same pattern of digits as in the last row of layer $W_j$, i.e., a row of ones. They will fill the last row of layer $W_{j+1}$. This completes the proof of the inductive thesis.
The number $p_n$ defined in the problem is the ratio of the number of zeros in the rows numbered from $0$ to $2^n$ to the number of all elements in these rows. These rows cover the layers $W_0, W_1, \ldots, W_n$ and the first row of layer $W_{n+1}$. From the relationship proved above, it follows that in the sum of layers $W_0, \ldots, W_j$ there are three times as many ones as in the sum of layers $W_0, \ldots, W_{j-1}\ (j = 1, 2, 3, \ldots)$, and since there is one one in layer $W_0$, there are $3^n$ ones in the sum of layers $W_0, \ldots, W_n$. Adding to this the two extreme ones of the next row, we see that there are $a_n = 3^n + 2$ ones in the considered fragment of Pascal's triangle. The total number of elements in this fragment is $b_n = 1 + 2 + 3 + \ldots + (2^n + 1) = (2^n + 1)(2^n + 2) / 2$, and thus there are $b_n - a_n$ zeros. The probability in question is

\[
\frac{b_n - a_n}{b_n} = \frac{(2^n + 1)(2^n + 2) / 2 - (3^n + 2)}{(2^n + 1)(2^n + 2) / 2}
\]

Hence,

\[
\lim_{n \to \infty} p_n = 1
\]