0
$\begingroup$

Let $A=\{1,2,3,...,100\}$. In how many ways $a_1\lt a_2\lt a_3\lt a_4\lt a_5, a_i \in A$ can be chosen from $A$ such that $a_p -a_i \geqslant 2$ for $(p-i)=1$

My try: From $A$ we can choise 5 distinct element by ${100 \choose 5}$ ways. If distance of two $a_i$ is exactly 1 then first element can be chosen by ${96 \choose 1}$ ways and rest 4 can be chosen by the consecutive of one another. So the way to pick 5 elements such that $a_p -a_i \geqslant 2$ for $(p-i)=1$ is ${100 \choose 5} - {96 \choose 1}$. Please see that am I right or wrong. Also another approches are also welcome. Thank you in advance

$\endgroup$
2
  • $\begingroup$ The problem asks that you don't have any pair next to each other, so you need to subtract $\{1,4,5,9,17\}$ which your calculation does not do. You will need to use inclusion/exclusion for cases that have more than one pair next to each other if you follow your approach. $\endgroup$ Commented Jun 6, 2021 at 14:04
  • 1
    $\begingroup$ One approach here is to consider the gaps, $g_1, \cdots, g_6$ between your numbers (including the gaps before $a_1$ and after $a_5$). These must sum to $95$ (why?). All of these are non-negative integers, and $g_2, g_3,g_4, g_5$ must be strictly positive. After a little algebra, Stars and Bars can be used. $\endgroup$ Commented Jun 6, 2021 at 14:09

1 Answer 1

1
$\begingroup$

Here is a way w/o explicitly using stars and bars

  • Take out $5$ balls, place $95$ remaining balls in a row, and color the $5$ balls taken out.

  • $95$ balls left will have $96$ interstices including the two ends.

  • The colored balls can be replaced in the interstices in $\binom{96}5$ "good" ways

  • The indices of the colored balls in each such arrangement are a valid choice

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.