# In how many ways can three soldiers be selected so that there are at least two soldiers standing between each selected soldier?

Ten soldiers are standing in a single row. Their commanding officer wants to select $3$ of them for a special mission if there have to be at least two soldiers standing between any two of the three soldiers selected. In how many ways the commanding officer select the soldiers?

My thoughts:

The ways of selection $3$ from $10$ is $120$. XX_ _ X _ _ _ _ _ , X are selected soldiers. They can arrange themselves in $3!$ ways and remaining soldiers in $7!$ ways. There can $2$ or more soldiers between them...so X can occupy other positions too. There can be more soldiers between other $2$ selected soldiers. I am unable to fit all the logic :(

• the ways of selection 3 from 10 is 120. XX_ _ X _ _ _ _ _ , X are selected soldiers. they can arrange themselves in 3! ways and remaining soldiers in 7! ways. there can 2 or more soldiers between them...so X can occupy other positions too. there can be more soldiers between other 2 selected soldiers. I am unable to fit all the logic :( – Nikita Dhiman Sep 27 '17 at 8:28
• When you pose a question here, it is expected that you include your own thoughts on the problem. For an exercise such as this, you should tell us what you have attempted and where you are stuck (in the question itself rather than the comments) so that you receive responses that address the specific difficulties you are encountering. – N. F. Taussig Sep 27 '17 at 8:33
• New to maths stack, thank for edit @N.F.Taussig – Nikita Dhiman Sep 27 '17 at 8:36

Method 1: Let $x_1$ be the number of soldiers before the first selected soldier; let $x_2$ be the number of soldiers between the first and second selected soldiers; let $x_3$ be the number of soldiers between the second and third selected soldiers; let $x_4$ be the number of soldiers after the third selected soldier. Then $$x_1 + x_2 + x_3 + x_4 = 7 \tag{1}$$ where $x_1, x_4 \geq 0$ and $x_2, x_3 \geq 2$. Let $x_2' = x_2 - 2$; let $x_3' = x_3 - 2$. Then $x_2'$ and $x_3'$ are nonnegative integers. Substituting $x_2' + 2$ for $x_2$ and $x_3' + 2$ for $x_3$ in equation 1 yields \begin{align*} x_1 + x_2' + 2 + x_3' + 2 + x_4 & = 7\\ x_1 + x_2' + x_3' + x_4 & = 3 \tag{2} \end{align*} Equation 2 is an equation in the nonnegative integers. A particular solution corresponds to the placement of three addition signs in a row of three ones. For example, $$1 + + 1 1 +$$ corresponds to the solution $x_1 = 1$, $x_2' = 0$, $x_3' = 2$, and $x_4 = 0$. The number of such solutions is $$\binom{3 + 3}{3} = \binom{6}{3}$$ since we must choose in which three of the six positions needed for three ones and three addition signs will be addition signs.

The number of outcomes is small enough that you check the answer by simply listing them.

Method 2: Line up six balls, each of a different color, none of which is red. Choose three of the six balls. Next, insert two red balls to the immediate right of each of the first two selected balls. Finally, number the balls from left to right. The numbers on the three balls you originally selected correspond to the positions of the selected soldiers. For instance, if we start with

$$\Large{\color{blue}{\bullet}\color{yellow}{\bullet}\color{magenta}{\bullet}\color{green}{\bullet}\color{orange}{\bullet}\color{purple}{\bullet}}$$

and select the blue, yellow, and purple balls, then insert two red balls to the immediate right of both the blue and yellow balls, we obtain

$$\Large{\color{blue}{\bullet}\color{red}{\bullet\bullet}\color{yellow}{\bullet}\color{red}{\bullet\bullet}\color{magenta}{\bullet}\color{green}{\bullet}\color{orange}{\bullet}\color{purple}{\bullet}}$$

so we select the first, fourth, and tenth soldiers.

Hence, there are $\binom{6}{3}$ ways of selecting the soldiers so that there at least two soldiers between each pair of selected soldiers.

The numbers are small enough it's easy to just enumerate the solutions manually.

Consider the outer two soldiers of the three selected. What's the closest together they may be in the line? There must be five soldiers between, and thus in this case the middle one of those five must be the third soldier selected.

How many ways are there of choosing the outer soldiers with exactly five men in between? It's four ways, times one possible middle soldier for each, equals four such possibilities total.

Then consider the next "width" up after seven. There are three ways to choose the outer men with six men between (for a "width" of eight inclusive of the outer men), and two choices for center man for each, so three times two is six.

The pattern continues easily, so the final total is:

$(4\times1)+(3\times2)+(2\times3)+(1\times4)=20$