, 2017

Solution:

Answer: $167$

Note that on the first step, Sam can either step on $2$ or $4$. On the second step, Sam can either step on $1$ or $3$, regardless of whether he is on $2$ or $4$. Now, for example, say that Sam takes $8$ steps. His total sum will be $2+1+2+1+2+1+2+1+2a$, where $a$ is the number of times that he decides to step on the larger number of his two choices. Solving gives $a=4$. As he took $8$ steps, this gives him $\binom{8}{4}=70$ ways in this case.

We can follow a similar approach by doing casework on the number of steps he takes. I will simply list them out here for brevity. For $8$ steps, we get $\binom{8}{4}=70$. For $9$ steps, we get $\binom{9}{3}=84$. For $12$ steps, we get a contribution of $\binom{12}{1}=12$. For $13$ steps, we get a contribution of $\binom{13}{0}=1$. Therefore, the final answer is $70+84+12+1=167$.