Probability of Successive Integers

Problem

Probability of Successive Integers, problem

Solution 1

The answer is $1 - {86 \choose 5}/{90 \choose 5} \approx 0.2076$.

The tricky part is counting the number of ways to choose $5$ non-adjacent numbers from $10$ through $99.$ Below I show that this is $\displaystyle {86\choose 5}$ using a 1-1 correspondence involving adding/removing padding to bit-strings.

For simplicity, it is helpful to first subtract $9$ from each number, so they range from $1$ through $90.$

Choose $5$ non-adjacent numbers from $1$ through $86.$ Write them as a bit string in which there is a $1$ in position $N$ just when $N$ was chosen.

For example, the choice $\{2,3,6,8,86\}$ would look like this:

$\overbrace{0110010100\dots001}^{\mathrm{\ (86\ bits)}}$

Now add a zero between each pair of ones. That will be four additional zeros. The string becomes:

$\overbrace{01010001001000\dots001}^{\mathrm{\ (90\ bits)}}$

The second string represents $5$ numbers chosen from $1$ through $90$ with no adjacent numbers. To convert any such string to a selection of numbers from $1$ through $86,$ remove a zero between each pair of ones.

Solution 2

First, consider the event that no two chosen numbers are adjacent. Let the five chosen numbers sorted in increasing order be $a_j~(j=1,2,\ldots,5)$. Define five groups of consecutive numbers: $G_1=(a_1,\ldots,a_2-1)$, $G_2=(a_2,\ldots,a_3-1),$...,$G_4=(a_4,\ldots,a_5-1)$, and $G_5=(a_5,...,99)$. Note, numbers less that $a_1$ don't fall in any of the five groups. Lump those numbers in a group $G_0$. For no two of the five numbers to be adjacent, the groups $G_1-G_4$ need to have at least two elements. $G_5$ will have at least one element as $a_5\leq 99$, and $G_0$ can have no element. If $N_i$ is the number of elements in group $G_i$, the number of ways of choosing the numbers under the constraint is the number of solutions of $N_0+N_1+N_2+\ldots+N_5=90$ such that $N_i\geq2$ for $0\lt i\lt 5$, $N_5\geq 1$, and $N_0\geq 0$. This is equivalent to the number of solutions of $N_0+N_1+N_2+\ldots+N_5=90-4+1=87$ under the modified constraint $N_i\geq 1$. The number of solutions is ${87-1\choose 6-1}={86\choose 5}$.

Thus, the required probability is $\displaystyle 1-{86\choose 5}/{90\choose 5}\approx 0.207$.

Solution 3

Count choices which fail. All are given uniquely by:

Start with even numbers. Starting with the highest and working down randomly decide whether to increment it and all higher numbers. If the highest is 96 or 98 we can choose to increment max 3 or 1 times.

$\displaystyle 1-\frac{{43\choose 5}\times 2^5+{43\choose 4}\times 26+{44\choose 4}\times 6}{{90\choose 5}}$

Exact result: $\displaystyle\frac{106081}{511038}.$

Solution 4

We can use the urn model we've used before. Let $x_2, \ldots, x_5 \ge 1,$ $x_1 \ge 9,$ $x_6 \ge 0$ and $x_1+\ldots+x_5+x_6 = 99-5 = 94.$ Our numbers $y_i$ for $i = 1,2,3,4,5$ equal $y_i = x_1+\ldots+x_i + i.$ The number of ways to assign these values is $\displaystyle {94-4-9+5\choose 5} = {86\choose 5},$ hence $\displaystyle p = 1-{86\choose 5}/{90\choose 5}.$

Acknowledgment

This is problem 2 from the Kurschak Contest 1970. Caame across that problem in Arbelos (1983, v 2, n 3, p 13), a now defunct magazine published by Samuel L. Greitzer.

Solution 1 is by Josh Jordan; Solution 2 is by Amit Itagi; Solution 3 is by Stephen Morris; Solution 4 is by Christopher D. Long.

 

|Contact| |Up| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

71491263