In how many ways you can make an unordered selection of four positive integers each less than or equal $25$ such that every pair of selected integers differ by at least $3$, i.e. for any two such integers $a$ and $b$, $d(a,b) = |a-b| \geq 3 $?

We can choose $x_1$ in 25 no of ways. We cannot choose $x_2$ to be $x_1-2$,$x_1-1$,$x_1$,$x_1+1$ or$x_1+2$. If $x_1$ is between 3 to 23, we choose $x_2$ in 20 ways. If $x_1 = 2$ or $x_1 = 24$, then no of ways is 21 and $x_1 = 1$ or $x_1 = 25$, then no of ways is 22 ways. While choosing $x_3$, there will be more such cases. Now I'm completely lost.

  • 2
    Welcome to MSE. It will be more likely that you will get an answer if you show us that you made an effort. This should be added to the question rather than in the comments. – José Carlos Santos Aug 10 at 9:21
  • @JoséCarlosSantos ohkay. I'm uploading my work and doubts in the problem. – Rambo8gunner Aug 10 at 9:28
up vote 1 down vote accepted

Imagine the integers as four balls, arrange them in a line, and glue two dummy balls to the right of the first three of them. That's $10$ balls in $4$ units; now add $15$ more balls, which makes $25$ balls and $19$ units. There are $\binom{19}4=3876$ ways to choose positions for the $4$ original units among the $19$ units, and they correspond to the solutions for your problem.

Suppose the selected numbers are $a_1, a_2, a_3, a_4$, where $a_1 \leq a_2 \leq a_3 \leq a_4$. Let \begin{align*} x_1 & = a_1\\ x_2 & = a_2 - a_1\\ x_3 & = a_3 - a_2\\ x_4 & = a_4 - a_3\\ x_5 & = 25 - a_4 \end{align*} Then $$x_1 + x_2 + x_3 + x_4 + x_5 = 25 \tag{1}$$ where $x_1 \geq 1$, $x_2 \geq 3$, $x_3 \geq 3$, $x_4 \geq 3$, and $x_5 \geq 0$.

Let \begin{align*} x_1' & = x_1 - 1\\ x_2' & = x_2 - 3\\ x_3' & = x_3 - 3\\ x_4' & = x_4 - 3\\ x_5' & = x_5 \end{align*} Then each $x_i'$ is a nonnegative integer. Substituting $x_1' + 1$ for $x_1$, $x_2' + 3$ for $x_2$, $x_3' + 3$ for $x_3$, $x_4' + 3$ for $x_4$, and $x_5'$ for $x_5$ in equation 1 yields \begin{align*} x_1' + 1 + x_2' + 3 + x_3' + 3 + x_4' + 3 + x_5' & = 25\\ x_1' + x_2' + x_3' + x_4' + x_5' & = 15 \tag{2} \end{align*} Equation 2 is an equation in the nonnegative integers. A particular solution of equation 2 corresponds to the placement of four addition signs in a row of fifteen ones. For instance, $$1 1 + 1 1 1 1 1 + + 1 1 1 1 1 1 1 + 1$$ corresponds to the solution $x_1' = 2$, $x_2' = 5$, $x_3' = 0$, $x_4' = 7$, $x_5' = 1$ (which corresponds to the solution $x_1 = 3$, $x_2 = 8$, $x_3 = 3$, $x_4 = 10$, $x_5 = 1$ and the selection $a_1 = 3$, $a_2 = 11$, $a_3 = 14$, $a_4 = 24$). The number of solutions of equation 2 is $$\binom{15 + 5 - 1}{5 - 1} = \binom{19}{4}$$ since we must select which four of the nineteen positions required for fifteen ones and four addition signs must be filled with addition signs. Thus, there are $\binom{19}{4}$ ways to make an admissible selection.

To see why, line up nineteen balls, each of a different color, none of which is red. Choose four of those nineteen balls. Next, insert two red balls to the immediate right of each of three leftmost selected balls. Finally, number the balls from left to right. The numbers on the four balls that were originally selected constitute the desired set of four balls selected from the first $25$ positive integers in which each pair of successive numbers differ by at least three.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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