0
$\begingroup$

A finite sequence of numbers $(a_1, \dots, a_n)$ is said to be $alternating$ if $$ a_1>a_2,\hspace{.2cm} a_2<a_3,\hspace{.2cm} a_3>a_4,\hspace{.2cm} a_4<a_5, \dots $$ $$ \mbox{or } a_1<a_2,\hspace{.2cm} a_2>a_3,\hspace{.2cm} a_3<a_4,\hspace{.2cm} a_4>a_5, \dots $$ How many alternating sequences of length $5$, with distinct numbers $a_1,a_2, \dots, a_5$ can be formed such that $a_i \in \{1,2,\dots,20\}$ for $i=1, \dots, 5$?

Source: ISI BMATH, BSTAT Entrance Exa, 2020: https://fractionshub.com/i-s-i-b-stat-b-math-2020/ (Problem 8)

Tried this question in the exam but failed. Any help will be truly appreciated.

$\endgroup$
2
  • 2
    $\begingroup$ I think the basic idea is, given $5$ distinct integers, find how many ways there are to arrange them into an alternating list. Then just multiply this result by ${}_{20}\mathrm{C}_5$. $\endgroup$ – K.defaoite Sep 21 '20 at 15:56
  • $\begingroup$ I think different combinations can give different results. $\endgroup$ – Sayantan Sep 21 '20 at 16:00
2
$\begingroup$

Let us choose any $5$ numbers $b_1,b_2,b_3,b_4,b_5$ from $\{1,2,\cdots, 20\}$ such that $$b_1<b_2<b_3<b_4<b_5$$ We can do this in $N=\binom{20}5$ ways. For each of these $N$ ways, we need to find how many alternating sequences can be made out of $b_1,b_2,b_3,b_4,b_5$.

Now, for a sequence $a_1,a_2,a_3,a_4,a_5$ to be an alternating sequence of the second type in the question, we need $$a_2>a_1,a_3 \text{ and } a_4>a_3,a_5 $$

    i.e.
  1. $a_2$ has at least two elements in the set $\{a_i| 1\le i \le 5\}$ less than $a_2$
  2. $a_4$ has at least two elements in the set $\{a_i| 1\le i \le 5\}$ less than $a_4$

So, to make an alternating sequence of the second type out of $b_1,b_2,b_3,b_4,b_5$ (note that $b_i<b_j \iff i<j$ by our choice of naming)

  • $a_2 \in \{b_3,b_4,b_5\}, \ a_4 \in \{b_3,b_4,b_5\}\implies $ We have $3$ options for $a_2$ and since $a_2\ne a_4$, only $2$ remaining choices for $a_4$.
    Thus $a_2,a_4$ can be chosen in $3.2=6$ ways.
    • If one of $a_2,a_4$ is chosen to be $b_3$, then the two elements on either sides of it $\underline{\text{need to be}}$ $b_1$ and $b_2$, so in such a case, we can have two places for $b_3$ to be in the alternating sequence, as $a_2$ or as $a_4$, in either case, the left and right elements of $b_3$ can be $(b_1,b_2)$ or $(b_2,b_1)$, and the remaining two elements $b_4,b_5$ having a strict order between are automatically assigned as $a_5,a_4$ respectively or $a_1,a_2$ respectively, correspondingly as $b_3$ is assigned as $a_2$ or $a_4$.
      Thus, if $b_3\in\{a_2,a_4\}$, we have $2\times 2=4$ ($2$ for $b_3$, $2$ for $b_1$ and $b_2$) choices to form an alternating sequence.
    • If $a_2$ and $a_4$ are from the set $\{b_4,b_5\}$, then the remaining elements $b_1,b_2,b_3$ all being smaller than them can be assigned to $a_1,a_3,a_5$ however we want, thus we have to assign one value each from $\{b_1,b_2,b_3\}$ to $\{a_1,a_3,a_5\}$, which can be done in $3!=6$ ways, and one value each from $\{b_4,b_5\}$ to $\{a_2,a_4\}$ which can be done in $2!=2$ ways, which, being independent choices, can be multiplied to give a total for $6\times 2=12$ choices for this case.

    So there are $12+4=16$ alternating sequences of the second type for each choice of $5$ distinct numbers $b_1,\cdots,b_5$, i.e. there are $16\times \binom{20}5$ alternating sequences of the second type.

    Similarly, try to find the number of alternating sequences of the first type in the question (by trying to find a set of rules like 1. and 2. above and counting the number of ways) and add these two numbers.

    $\endgroup$
    2
    • $\begingroup$ Doesn't seem correct suppose selection of 5 is 1,2,3,4,5 then for alternating patternof second type a/q OP ,let a2 and a4 be 3 and 5 now let a3 be 4 clearly inequality is violated. $\endgroup$ – Aditya Prakash Sep 22 '20 at 21:13
    • $\begingroup$ @AdityaPrakash you are right, that was overseeing on my part. I'll correct it up. $\endgroup$ – Fawkes4494d3 Sep 22 '20 at 22:18

    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.