Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Out of 20 consecutive natural numbers, in how many ways 4 numbers can be selected such that any two selected number differ by at least 3.

I am not able to proceed further than writing domain of each number( x, y, z, w be the numbers in increasing order).

$ x \le 11$

$ x +3 \le y \le 14$

$ y +3 \le z \le 17$

$ z +3 \le w \le 20$

How can I proceed? Thanks

share|cite|improve this question
up vote 3 down vote accepted

Instead of selecting four numbers out of $\{1,\ldots,20\}$, select four numbers $x_1<x_2<x_3<x_4$ out of $\{1,\ldots,14\}$ and let $y_1=x_1$, $y_2=x_2+2$, $y_3=x_3+4$, $y_4=x_4+6$. Then $(y_1,y_2,y_3,y_4)$ has the properties required and any allowed quadruple can be obtained this way. Therefore the answer is $14\choose 4 $ (or in general $n-(k-1)(d-1)\choose k$ for choosing $k$ numbers out of $n$ with distance at least $d$).

share|cite|improve this answer

Think of the four chosen numbers as dividers, breaking the string of integers from $1$ through $20$ into five sections. For instance, if you choose $5,10, 17$, and $20$, the picture looks like this:

                        5   10     17 20

The first section, before the $5$, contains four numbers; the second, between $5$ and $10$, also contains four numbers; the third, between $10$ and $17$, contains six numbers; the fourth, between $17$ and $20$, contains two numbers; and the fifth, after $20$, contains none.

Let $u_1,u_2,u_3,u_4$, and $u_5$ be the number of numbers in the respective sections. There are $16$ other numbers, and there must be at least two of them between adjacent dividers, so $u_1,u_2,u_3,u_4$, and $u_5$ must satisfy the following conditions:

  1. $u_1+u_2+u_3+u_4+u_5=16$, and
  2. $u_1,u_5\ge 0$, $u_2,u_3,u_4\ge 2$.

Moreover, each set of integers satisfying those solutions describes one of the solutions to your problem, so you just need to count the solutions to (1) satisfying (2). In fact, we can simplify this even further if we let $v_2=u_2-2,v_3=u_3-2$, and $v_4=u_4-2$. Then we need only count the non-negative solutions to $u_1+v_2+v_3+v_4+u_5=10$, which is a standard stars-and-bars problem.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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