Let $n$ be a natural number and $C$ a non-negative real number. Determine the number of sequences of real numbers $1, x_{2}, ..., x_{n}, 1$ such that the absolute value of the difference between any two adjacent terms is equal to $C$.
Problem
Source:
Tags: absolute value, combinatorics
21.04.2018 16:29
Start with $x_1=1$ and build $x_2,x_3,...,x_{n+1}$ in that order. The only possible operations are adding $C$ to the previous term (which we call $-C$ operation), or subtracting $C$ to the previous term (which we call $-C$ operation). To archive $x_{n+1}=1$, we must use equal amount of $+C$ and $-C$ operation. There are $n$ operations, hence the answer is $$\begin{cases} \dbinom{n}{\frac{n}{2}} & n\text{ even} \\ 0 & n\text{ odd} \end{cases}$$
22.04.2018 23:30
MarkBcc168 wrote: Start with $x_1=1$ and build $x_2,x_3,...,x_{n+1}$ in that order. The only possible operations are adding $C$ to the previous term (which we call $-C$ operation), or subtracting $C$ to the previous term (which we call $-C$ operation). To archive $x_{n+1}=1$, we must use equal amount of $+C$ and $-C$ operation. There are $n$ operations, hence the answer is $$\begin{cases} \dbinom{n}{\frac{n}{2}} & n\text{ even} \\ 0 & n\text{ odd} \end{cases}$$ You missed out the case where $C = 0$. In that case, $\forall N \in \mathbb{N}$, there is exactly one sequence $1,1,1,1,...,1$ that satisfies the conditions.