Number of sequences that satisfy the absolute difference condition

Question

Let $x_0 =0$ and let $x_1,.....x_{10}$ satisfy that $|x_i - x_{i-1}|$ = 1 for 1≤i≤10 and $x_{10} = 4$ . How many such sequences are there satisfying these conditions?

I tried to calculate it by backtracking from $x_0$ and $x_{10}$, and built an entire tree for the possible values. Based on the edges of the trees, I calculated the answer to be $2*4*6*7*7*7*7*6*4*2$ but the answer is clearly wrong. The question is supposed to be a probability question, but I was thinking of trying to solve it using dynamic programming. It is supposed to be an easy question though, can anyone help me out?

Answer 1

$x_i$ is either $x_{i - 1} + 1$ or $x_{i - 1} - 1$, right?

Then this is equivalent to you perform $+1$ or $-1$ by $10$ times, and expecting a result of $4$.

Simple calculation: If we choose to $+1$ by $x$ times, then $-1$ should be $(10 - x)$ times, and the result is $x \cdot (+1) + (10 - x) \cdot (-1) = 2 x - 10$, to ensure this equal to $4$, we must have $x = 7$.

Then the problem is to choose $7$ positions among $10$, and assign them to be $+1$, the rest $3$ positions are assigned by $-1$.

The answer is $\dbinom{10}{7} = 120$.

Answer 2

Let $x_0 =0$ and let $x_1,.....x_{10}$ satisfy that $|x_i - x_{i-1}|$ = 1 for 1≤i≤10 and $x_{10} = 4$

Alternative approach:
nowhere near as elegant as the response of PinkRabbit.

From the problem constraints, you have that for $~i \in \{0,1,2,\cdots,8\},~$ that $~x_{i+2} - x_i \in \{-2,0,2\}.~$

Further, as $~x_i~$ goes to $~x_{i+2},~$ there is exactly 1 way that $~x_{i+2} - x_i = 2,~$ (i.e. $~x_{i+1} - x_1 = 1 = x_{i+2} - x_{i+1}~$) exactly 1 way that $~x_{i+2} - x_i = -2,~$ and exactly 2 ways that $~x_{i+2} - x_i = 0.$

Let

• $~y_1 = x_2 - x_0.$
• $~y_2 = x_4 - x_2.$
• $~y_3 = x_6 - x_4.$
• $~y_4 = x_8 - x_6.$
• $~y_5 = x_{10} - x_8.$

Then, examine each element (i.e. solution) in the collection of solutions to:

• $~y_1 + y_2 + y_3 + y_4 + y_5 = 4,~$

• For $~i \in \{1,2,3,4,5\}, ~y_i \in \{0,-2,2\}.$

For each such solution, if exactly $~k~$ of the variables are equal to $~0,~$ then attach a weight of $~2^k~$ to that solution. This corresponds to there being exactly two ways of achieving $~x_{i+2} = x_i.~$

It is immediate that none of the solutions can have all $~5~$ of the variables equal to $~0.~$ Also, because there are $~5~$ variables involved, and the sum is $~4,~$ the number of variables equal to $~0~$ must be odd.

Therefore, each satisfying solution will have either exactly 1 of the variables equal to $~0,~$ or exactly $~3~$ of the variables equal to $~0.~$

---

$\underline{\text{Case 1: Exactly} ~1 ~\text{variable} ~= 0}$

There are $~\displaystyle\binom{5}{1}~$ choices for the variable equal to $~0.~$ Then, since $~3~$ of the $~4~$ remaining variables must be equal to $~+2,~$ rather than $~-2,~$ there are then $~\displaystyle\binom{4}{1}~$ choices for the variable equal to $~-2.~$

Therefore, the enumeration for Case 1 is

$$5 \times 4 \times 2^1 = 40.$$

---

$\underline{\text{Case 2: Exactly} ~3 ~\text{variables} ~= 0}$

There are $~\displaystyle \binom{5}{3}~$ choices for the $~3~$ variables equal to $~0.~$ Once these variables are set, the other two variables must each be set to $~+2.~$

Therefore, the enumeration for Case 2 is

$$\binom{5}{3} \times 2^3 = 80.$$

---

$\underline{\text{Final Computation}}$

$$40 + 80 = 120.$$