5
$\begingroup$

Number of ways in which $4$ people can be selected out of $10$ people sitting in a row such that exactly two are consecutive is?

My attempt:

I tried two approaches:

  1. PIE: required ways = total ways - ways in which three are consecutive + ways in which four are consecutive. But I do not know how to calculate "ways in which three are consecutive", so I am stuck.
  2. Direct: the problem is that:

    • If I select two people at the ends: - - 3 4 5 6 7 8 9 10 or 1 2 3 4 5 6 7 8 - -, then I have six more ways to select the third person, but am unsure about the fourth way.
    • If I select two people in the middle, like so 1 2 3 - - 6 7 8 9 10, then selecting the next two people is troublesome, as the seats 1 and 2 cannot be occupied.

Both these approaches seem cumbersome. I hope there's a simpler way. What is that?

$\endgroup$
5
+50
$\begingroup$

Method 1: Suppose we have four green balls, two of which are placed in a box, and six blue balls. Line up the six blue balls in a row. This creates seven spaces, five between successive blue balls and two at the ends of the row. Choose one of these seven spaces for the box with two green balls. Choose two of the remaining six spaces for the other two green balls. Now number the balls from left to right. The numbers on the green balls represent the positions of the selected people. Notice that exactly two of the green balls are consecutive, namely the ones in the box. Hence, there are $$\binom{7}{1}\binom{6}{2} = 105$$ ways to select four people from a row of $10$ people so that exactly two of the adjacent people are consecutive.

Observe that this is essentially your second method condensed into a single step. There are five ways to place the box with two green balls between two blue balls and two ways to place the box at an end of the row of six blue balls. This accounts for the factor of $7$. In each case, we are left with six spaces, two of which must be filled with the remaining green balls.

Method 2: In your first approach, you overlooked the possibilities that no two selected people are adjacent and that two separated disjoint pairs of adjacent people are selected. There are $\binom{10}{4}$ ways to select four of the ten people. From these, we must exclude the four cases below.

No two selected people are adjacent: We line up six blue balls in a row, creating seven spaces. We choose four of these seven spaces in which to place a green ball, then number the balls from left to right. The numbers on the green balls represent the positions of the selected people. There are $\binom{7}{4}$ such cases.

Two separated disjoint pairs of adjacent people are selected: We line up six blue balls in a row, creating seven spaces. We choose two of the seven spaces in which to place two boxes, each of which contains two green balls, then numbers the balls from left to right. The numbers on the green balls represent the positions of the selected people. There are $\binom{7}{2}$ such cases.

A block of three consecutive people and a fourth person not adjacent to them are selected: We line up six blue balls in a row, creating seven spaces. We choose one of the seven spaces for a box with three green balls and one of the remaining six spaces for the other green ball, then number the balls from left to right. The numbers on the green balls represent the positions of the selected people. There are $\binom{7}{1}\binom{6}{1}$ such cases.

A block of four consecutive people is selected: We line up six blue balls in a row, creating seven spaces. We choose one of the seven spaces for a box with four green balls, then number the balls from left to right. The numbers on the green balls represent the positions of the selected people. There are $\binom{7}{1}$ such cases.

Thus, the number of permissible selections is $$\binom{10}{4} - \binom{7}{4} - \binom{7}{2} - \binom{7}{1}\binom{6}{1} - \binom{7}{1} = 105$$

$\endgroup$
3
$\begingroup$

Direct method: let the people be $1,2,...,10$.

Consider two consecutives: $$\begin{align} &1,2: \ {7\choose 2}-{6\choose 1}=15 \\ &2,3: \ {6\choose 2}-{5\choose 1}=10\\ &3,4: \ {6\choose 2}-{4\choose 1}=11\\ &\vdots\\ &7,8: \ {6\choose 2}-{4\choose 1}=11\\ &8,9: \ {6\choose 2}-{5\choose 1}=10\\ &9,10: \ {7\choose 2}-{6\choose 1}=15.\end{align}$$ Hence, the sum is $105$.

$\endgroup$
  • $\begingroup$ I mean, yeah, a brute force method is always there in any given question, but...it's so boring! :( But, thankfully there was some symmetry in here, so it's reasonably calculable anyway! :) $\endgroup$ – Gaurang Tandon Apr 3 '18 at 13:50
2
$\begingroup$

$C(7,1)*C(5,1)+(C(6,2)-C(5,1))*7=105$

(first part) + (last part):

the first part: First, choose consecutive $4$ blocks, there are only $7$ ways to do it. Then choose $2$ consecutive blocks from the others, and we have $5$ ways to do it. Once we finish the select we can insert the $4$ consecutive blocks into the $2$ consecutive blocks

select 4 consecutive positions enter image description here

last part: Now consider the other cases, I failed to choose the $2$ consecutive blocks from the other blocks, so there should be $C(6,2)-C(5,1)$ ways that fails. Now since there are $6$ blocks and we choose only $2$, which are not consecutive, we have $6+1$ ways to insert the $4$ consecutive blocks from the first part.

This finish the proof.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.