Four pairs of integers are selected at random from 1 to 26. What is the probability that the sum of any pair does not exceed 26?

Question

If only one pair is selected then the probability is simply $\frac{26\cdot12}{26\cdot25}$. But how to solve the problem with several pairs that are jointly (not independently) drawn?

Answer 1

I wrote a computer program to slog through all the possibilities, and also a Monte Carlo program. The results agree and are: 1 pair: 12/25 = 0.48 (easily done by hand); 2 pairs: 374/1725 ~ 0.216812; 3 pairs: 44/483 ~ 0.091097; 4 pairs: 13408/382375 ~ 0.035065 (much less than 1/16). This may be useful as a check if anyone finds a better method.

Answer 2

There are $\tfrac1{4!}\tbinom{26}2\tbinom{24}2\tbinom{22}2\tbinom{20}2=164038875$ ways to choose a set of four disjoint pairs of integers from the set $\{1,2,3,\ldots 26\}$.

Suppose we have chosen four pairs, such that for each pair the sum is no greater than $26$. Let $S$ be the union of all the pairs, containing eight elements. Then $S$ cannot contain more than four integers greater than $13$, and any such integer must be paired with an integer smaller than $13$.

Consider the case in which the union $S$ contains four elements $w,x,y,z$ such that $13<w<x<y<z<27$. It must also contain four elements $a,b,c,d$ such that $0<a<b<c<d<14$. What can those elements be?

Say we choose $z$ first. Then it must be paired with a number below or equal to $26-z$. After that we choose $y$ such that $13<y<z$. It must be paired with a number below or equal to $26-y$, but not equal to the number paired with $z$. After that we choose $x$, and so on.

$$\begin{matrix}.]&.&.&.&.&.]&.&.&.&.&[.\\\hline 0&26-z&26-y&26-x&26-w&13&w&x&y&z&26\end{matrix}$$

Thus for any specific $(w,x,y,z)$ there are $(26-z)(26-y-1)(26-x-2)(26-w-3)$ choices for $(w',x',y',z')$, where $w$ is paired with $w'$, etc.

$$\begin{align*}&\sum_{13<w<x<y<z<27} (26-z)(26-y-1)(26-x-2)(26-w-3) \\=&\sum_{0<a<b<c<d<13} a(b-1)(c-2)(d-3) \\=&\sum_{0<a\le b\le c\le d<10} abcd \\=&\lbrace\textstyle{13\atop 9}\rbrace \end{align*}$$

where $\lbrace{n\atop k}\rbrace$ denotes the Stirling number of the second kind.

Now consider the case in which the union $S$ contains exactly three elements $x,y,z$ such that $13<x<y<z<27$. We can pair off these elements as shown above; finally, both elements of the last pair are no greater than $13$, and can be selected from those left over in $\tbinom{13-3}2=45$ ways. Thus we count

$$\begin{align*}&\tbinom{10}{2}\sum_{0<a\le b\le c<11} abc \\=&\tbinom{10}{2}\lbrace\textstyle{13\atop 10}\rbrace\end{align*}$$

The remaining cases, in which there are two elements greater than $13$, or one, or none, can be treated in the same way. Summing all the cases together, we get

$$\lbrace\textstyle{13\atop 9}\rbrace +\tbinom{10}{2}\lbrace\textstyle{13\atop 10}\rbrace +\tfrac{1}{2!}\tbinom{11}{2}\tbinom{9}{2}\lbrace\textstyle{13\atop 11}\rbrace +\tfrac{1}{3!}\tbinom{12}{2}\tbinom{10}{2}\tbinom82\lbrace\textstyle{13\atop 12}\rbrace +\tfrac{1}{4!}\tbinom{13}{2}\tbinom{11}{2}\tbinom92\tbinom72$$

which equals $5752032$. On dividing this number by $164038875$, we obtain the probability $0.035065054$ or about $3.5\%$.