7
$\begingroup$

We have a sequence $a_1,a_2,...,a_n$ and $\forall i\in N;~~~ a_i\in\{1,2,3,...,n\}$. A sequence is $GOOD$ if we have that: For Every $k \in N$, we have $a_k≥a_i$ for every $i<k$, or $a_k≤a_i$ for every $i<k$. it means that every element is larger than all previous elements or smaller than all previous elements.

We want to find how many permutations of $1,2,3,...n$ are $GOOD$ ?

It was a question in an old exam and the answer was $2^{n-1}$ it said that in every choice, we can put the biggest or the smallest element from the remaining numbers, except that for the last one we have one choice so the answer is $2^{n-1}$. I don't completely understand this answer. (eg. if we follow this algorithm it could easily get to the point where we can't choose any other number: $1\to 1, \ n \to ?$ Can anyone explain this answer or give another answer for this question? Is this answer correct?

PS. Changed the condition so it is better understandable.

$\endgroup$
  • 3
    $\begingroup$ sorry, why isn't the answer just $2$? $\endgroup$ – lulu Feb 25 at 21:33
  • $\begingroup$ @lulu I am wondering about the same thing, definitely missing something $\endgroup$ – Vinyl_cape_jawa Feb 25 at 21:34
  • 2
    $\begingroup$ I think the question is written incorrectly. It should be "for every $k \in N$, we have $a_k \geq a_i$ for all $i < k$ or $a_k \leq a_i$ for all $i < k$". So an example of a good sequence is $3456721$ $\endgroup$ – Dan Rust Feb 25 at 21:35
  • $\begingroup$ @Vinyl_coat_jawa My only guess is that the OP doesn't know what "permutation" means. Maybe strings like $1,1,1,1\cdots,1$ are allowed. $\endgroup$ – lulu Feb 25 at 21:35
  • 1
    $\begingroup$ Your edit has clarified things slightly. But when you say $a_k\ge a_i$ or $a_k\le a_i$ for every $i<k$, you are making two mistakes: first, it should be $>$ and $<$ instead of $\ge$ and $\le$; and secondly, it should be "$a_k > a_i$ for every $i<k$, or $a_k < a_i$ for every $i<k$". $\endgroup$ – TonyK Feb 25 at 21:42
2
$\begingroup$

Note that the first two elements in the sequence must be adjacent to each other, but their order is irrelevant. So given a GOOD sequence $a_1,\ldots,a_n$ of length $n$, we can generate two GOOD sequences of length $n+1$:

$$a_1,a_1+1,b_2,\ldots,b_n$$ and $$a_1+1,a_1,b_2,\ldots,b_n$$

where $b_i=a_i$ if $a_i<a_1$, and $b_i=a_i+1$ if $a_i>a_1$. For instance, the sequence $23145$ generates $234156$ and $324156$. So we see that there are twice as many GOOD sequences of length $n+1$.

$\endgroup$
  • $\begingroup$ If I don't get any complete non-inductive answers till tomorrow, I will select this answer as the best because the complete solution of this answer is submitted earlier than the other(s). Thank you very much. $\endgroup$ – amir na Feb 25 at 22:25
3
$\begingroup$

Think about choosing the permutation in reverse order $a_n,a_{n-1},\dots,a_1$. Each element must be highest or smallest of the elements not previously chosen, so there are two choices for each (except for $a_1$, where the highest and lowest are the same).

For example, the last element is always $1$ or $n$. If the last element is $1$, then the second to last is either $2$ or $n$. And so on $\dots$.

$\endgroup$
  • $\begingroup$ Yes. And this explains the OP's question: the answer in the third paragraph makes perfect sense if we choose the elements backwards. $\endgroup$ – TonyK Feb 26 at 2:56
2
$\begingroup$

What I think the hint is trying to say:

Suppose that our current string is $a_1a_2a_3\cdots a_k$. Then either $a_{k+1}$ must be $\max\{a_1, \ldots, a_k\}+1$ or $\min\{a_1, \ldots, a_k\}-1$. If any other choice is made, then either $\max\{a_1, \ldots, a_k\}+1$ or $\min\{a_1, \ldots, a_k\}-1$ will not be legally allowed to be placed. Of course one needs to be careful with when either of these values doesn't exist (i.e. when either $1$ or $n$ has already been used). It's not clear to me how to fill in this gap.


Here's probably the simplest inductive argument.

Base cases up to $n=2$ are easy.

Suppose that the proposition is true for the case $n-1$.

First, notice that we have only two choice for $a_n$, as it must always be either $1$ or $n$. If not, then both $1$ and $n$ appear before $a_n$ (because $n \geq 3$) which means it can't be good.

If $a_n = 1$, then $a_1-1, \cdots a_{n-1}-1$ is a good sequence of length $n-1$, so there are $2^{n-2}$ choices for the other elements.

If $a_n = n$, then $a_1, \cdots a_{n-1}$ is a good sequence of length $n-1$, so there are $2^{n-2}$ choices.

In total then, there are $2^{n-2} + 2^{n-2} = 2^{n-1}$ choices.

$\endgroup$
  • $\begingroup$ But $a_1$ can be any number, so there are $n$ choices for it. I haven't figured out how to do the counting to justify $2^{n-1}$. I am thinking induction, starting with the GOOD sequences of $n$ and adding in $n+1$. If you start with $n+1$ you have to use the descending sequence. Otherwise $n+1$ can go anywhere after $n$ so we want to show there are $2^{n-1}-1$ choices for that. $\endgroup$ – Ross Millikan Feb 25 at 21:58
  • $\begingroup$ I think the hint in the question is nonsense, and your approach is doomed to failure. $\endgroup$ – TonyK Feb 25 at 22:01
  • $\begingroup$ @RossMillikan I understand most part of Dan Rust proof except that like you, I can't figure the $a_1$ because it has n choices (or at least n-2 if we don't count 1 and n). I think induction can be a good approach. $\endgroup$ – amir na Feb 25 at 22:04
  • $\begingroup$ "There is exactly one sequence...": no there isn't. Any sequence ending in $n$ will do, and there are $2^{n-2}$ of those. $\endgroup$ – TonyK Feb 25 at 22:16
  • $\begingroup$ @TonyK thanks, fixed. $\endgroup$ – Dan Rust Feb 25 at 22:25
1
$\begingroup$

We can prove it by strong induction. A GOOD sequence of length $n$ with $n$ in position $k$ consists of a GOOD sequence of the numbers from $n-k+1$ to $n-1$, followed by $n$, followed by the numbers from $1$ to $n-k$ in descending order. There is one sequence that starts with $n$ and has all the numbers in descending order.

The base case is $n=1$, where there is $2^{1-1}=1$ GOOD sequence. Assume we have shown there are $2^{n-1}$ GOOD sequences for $n$ up to $m$. Then for $m+1$ we have one sequence that starts with $m+1$ and $2^{k-2}$ for each position $k$ from $2$ through $m+1$ and $$1+\sum_{i=2}^{m+1}2^{i-2}=2^m$$

$\endgroup$

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.