How many possible different arrangements?

Question

There are $1000$ numbers $1,2,3,...999,1000$ to be arranged in a line so that every number other than the rightmost differs by 1 from one or more of the numbers to its right. How many different arrangements are possible?

If $1$ is the rightmost number, then there is only one possible arrangement, which is $1000,999,...,3,2,1.$ If $2$ is the rightmost number, then $1$ can be placed in any position. There are 1000−2+1=999 different arrangements. If $3$ or an even larger number is the rightmost number, then it becomes more complicated. Since the only restriction is that the numbers that are less than the rightmost number must have the larger numbers place on the right of the smaller numbers. For example, if $4$ is the rightmost number, then $1,2,3$ are the numbers that can be moved. Then $3$ must be on the right of $2$ and $2$ must be on the right of $1$.Then there are $\frac{((2015−3)+1)(2015−3)}{2}×(2015−3−1)$. So, how can I sum these up and find the total possible arrangements?

Answer 1

Here I have an inductive solution to this problem:

Let us denote the number of possible arrangements for $1,2,3...n$ be $T(n)$.

For $n = 1$ we have only one arrangement. $\therefore\ T(1) = 1$.

For $n = 2$ we have two arrangements $1,2$ and $2,1\ \therefore\ T(2) = 2$

Now we conjecture that $T(n) = 2^{n-1}$ which is valid for $n=1\ and\ n = 2$

We are now going to attempt the inductive step:

We take an arrangement $P(n) = a_1,a_2,..,a_n\ where\ a_i\in \{1,2,3,..n\}\ \forall\ i \in\{1,2,3,..n\}\ \ $

We note that $n+1$ can be placed at any position to the left of the position of $n$ in the arrangement. Other than that there is a case where $n+1$ can be placed to right of $n$ ,when the arrangement is $1,2,3,..,n,(n+1)$

Let $S(n) = a_1, a_2, a_3,.. a_n, a_{n+1}$ be an arrangement of $1,2,3..n,(n+1)$

Now, we denote the positions of a number in the arrangement to be $i$ if it is in the position $a_i$ in $S(n)$

Now, $(n+1)$ can be in position $1$ in $T(n) = 2^{n-1}$ cases as $a_1$ is the leftmost element in $S(n)$

When $(n+1)$ is in position $2$, $1$ must be in position $1$ and $2,3,4..n$ to the left of $(n+1)$. Now $2,3,4..n$ can be arranged in $T(n-1) = 2^{n-2}$ ways. Thus, $(n+1)$ can be in position $2$ in $2^{n-2}$ ways.

By similar arguments, we get that $(n+1)$ can be in position $p$ where $1\le p\le n$ in $T(n-p+1) = 2^{n-p}$ ways.

$(n + 1)$ can be in position $(n + 1)$ in only $1$ way where $1,2,3..n$ all lies to the left of $n+1$ resulting in the arrangement $1,2,3,..,n,(n+1)$

$\therefore T(n+1) \\= 2^{n - 1} + 2^{n - 2} + 2^{n - 3}+..+ 4 + 2 + 1 + 1 \\= \frac{2^{n} - 1}{2 - 1} + 1 \\= 2^{n} + 1 - 1 \\= 2^{n}$

$\therefore T(1000) = 2^{999}$

Hope that this helps.

Answer 2

A simpler solution. Hint: what can the leftmost number be?

Suppose we put some number $n$ other than the largest or smallest on the left. Look at the rightmost number which is smaller than $n$, call it $m$. Both $m+1$ and $m-1$ are at most $n$, so must be further left than $m$. So $m$ has be on the extreme right. But the same applies to the rightmost number bigger than $n$. They can't both be on the right, contradiction.
So the first number has to be either the smallest or largest. Similarly, the second number is either the smallest or largest of what remains, and so on. It is easy to check that if we just choose the smallest or largest of what is left at each stage, we always have a sequence that works, and so there are $2^{999}$ ways to do this ($2$ options at each step but the last).