Question

You and Ellie are playing a game, in which first Ellie chooses r numbers out of the set 1,2,,n, for 1 S n, and then you independently choose r numbers out of the same set. What is the probability that: (a) Your set of r chosen numbers do not include consecutive values? (b) Your set of r chosen numbers includes precisely one pair of consecutive values? (c) Given Ellie's selection, your numbers are precisely the same as hers? (d) Given Ellie's selection, there are precisely k, for 1Sk < r, of your numbers that match hers?

Answer 1

Let the numbers be denoted by X1, X2, .....Xn

Ans a)  Total number of ways to choose r numbers out of n numbers = ${n}\choose{r}$

Now, let's consider we split the set X1, X2, ...Xn into 2 sets of r and (n-r) elements respectively. Now, there are (n-r+1) gaps between the (n-r) numbers (including the ends), so to avoid numbers being consecutive, we need to insert the r numbers in those gaps (see the arrangement below where Y1, Y2, ...Y_n-r are the (n-r) numbers):

Y1 Y2 Y3 n-r

We can insert the r numbers into these (n-r) gaps in ${n-r}\choose{r}$ ways

$\therefore$ P(Set of r chosen values don't include consecutive values) = ${n-r}\choose{r}$ / ${n}\choose{r}$

Ans b) No. of ways to choose 2 consecutive values = n-1 (either X1X2 / X2X3/...../X_n-1X_n)

Without loss of generality suppose we choose Y1 and Y2 as the 2 consecutive values (can re-label the numbers otherwise so that the 2 consecutive chosen numbers are labelled Y1 and Y2). Now, looking at the above diagram, we cannot use the first 3 gaps. Hence, there are (n-r+1 - 3) = (n-r-2) gaps now to insert the remaining r-2 numbers into.

$\therefore$ number of possible selections = (n-1) *   

(n r22)

$\therefore$P(My r chosen values contain precisely 1 consecutive pair)  

= (n-1) *
(n r22)
/  ${n}\choose{r}$

Ans c)  Suppose Ellie has chosen Z1, Z2, ...Zr

This is only 1 among the ${n}\choose{r}$ possible ways in which I can make my selection.

Hence, P(My selection is same as Ellie's) = 1 / ${n}\choose{r}$

Ans d)  If Ellie's selections are Z1, Z2, ...Zr,

For precisely k of my selections to match that of Ellie's, it can happen in ${r}\choose{k}$ * ${n-k}\choose{r-k}$ ways (${r}\choose{k}$ ways to choose k numbers from r of Ellie's selections, and ${n-k}\choose{r-k}$ ways to choose rest of the r-k numbers from the remaining n-k numbers).

$\therefore$ P(Precisely k of my numbers match Ellie's) = ${r}\choose{k}$ * ${n-k}\choose{r-k}$ / ${n}\choose{r}$