8 distinct boxes are placed in a line. Each box contains at least 1 and at most 8 red balls. The maximum difference of the number of balls between adjacent boxes is 1. How many distinct cases are there of the number of balls in the boxes?
So I first started with labeling the boxes $a_1$ through $a_8$. Then we write the inequalities pertaining to the differences of the number of balls: $\lvert a_1 - a_2 \rvert \lt 1$, $\lvert a_2 - a_3 \rvert \lt 1$ and so on. However, this seems like it leads to a lot of messy casework. Is there any way to avoid this and maybe find a cleaner solution?
I don't usually deal with combinatorics, so there has to be more elegant solution, but here is what I got:
We are basically looking for number of sequences $(a_1,\ldots,a_8)$ such that
$$a_i\in\{1,\ldots,8\},\quad i=1,\ldots,8;$$ $$|a_{i+1}-a_{i}|\leq 1,\quad i=1,\ldots,7.$$
We can have $22$ possible different pairs of $(a_4,a_5)$: $8$ pairs of $(i,i)$, $7$ pairs of $(i,i+1)$ and 7 pairs of $(i+1,i)$. Notice that the number of sequences of length $4$ which lead to $a_4=i$, is the same as number of sequences of length $4$ that lead out of $a_5=i$. It means that if we know these numbers for each $i=1,\ldots,8$, then we can count all sequences by looking at all possible pairs $(a_4,a_5)$. For example, if we denote $l_i, l_j$ as numbers of possible sequences leading to $a_4=i$ and $a_4=j$ respectively, then the number of all sequences with $(a_4,a_5) = (i,j)$ is $l_i\cdot l_j$ (provided that $|i-j|\leq 1$).
We will only look at sequences leading out of $a_5 = 1,2,3,4$, because the numbers that we'll get are the same for $a_5 = 8,7,6,5$ respectively.
Let's start with the easiest case of $a_5=4$:
$$\begin{array}{c|c|c|c} a_5 & a_6 & a_7 & a_8\\ \hline & & &1\\ & &2&2\\ &3&3&3\\ 4&4&4&4\\ &5&5&5\\ & &6&6\\ & & &7 \end{array}$$
We can see that there are $3^3$ possible sequences that lead out of $a_5=4$, and all of them fit our rules. It means that $l_4 = l_5 = 27$, which is the number of sequences leading out of $a_5=4$ and number of sequences leading out of $a_5=5$. As noted before, this is also the number of sequences leading to $a_4=4$ and the number of sequences leading to $a_5=5$.
Let's look at $a_5=3$:
$$\begin{array}{c|c|c|c} a_5 & a_6 & a_7 & a_8\\ \hline & & &0\\ & &1&1\\ &2&2&2\\ 3&3&3&3\\ &4&4&4\\ & &5&5\\ & & &6 \end{array}$$
We see that there is one sequence, that doesn't fit our rules: one with $a_8=0$. It means that $l_3 = l_6 = 27-1 = 26$.
Now let's look at $a_5 = 2$:
$$\begin{array}{c|c|c|c} a_5 & a_6 & a_7 & a_8\\ \hline & & &-1\\ & &0&0\\ &1&1&1\\ 2&2&2&2\\ &3&3&3\\ & &4&4\\ & & &5 \end{array}$$ There is $1$ path that leads to $a_7=0$, and from there we get $3$ possible outcomes for $a_8$. There are also two paths that lead to $a_8=0$ through $a_7=1$. That means that there are $l_2=l_7=27-3-2=22$ sequences that fit our rules.
Let's look at the last case of $a_5 = 1$:
$$\begin{array}{c|c|c|c} a_5 & a_6 & a_7 & a_8\\ \hline & & &-2\\ & &-1&-1\\ &0&0&0\\ 1&1&1&1\\ &2&2&2\\ & &3&3\\ & & &4 \end{array}$$
There is $1$ path leading up to $a_6=0$, which then produces $3^2$ possible outcomes. There is $1$ path to $a_7=0$ through $a_6=1$, which produces $3$ possible outcomes. Lastly, there are $2$ paths leading up to $a_8=0$, where $a_6\neq 0$ and $a_7\neq 0$. It means that $l_1 = l_8 = 27 -9 - 3-2 = 13$.
We can now calculate numbers of sequences, that lead to each possible pair $(a_4,a_5)$. Let $N_{i,j} = l_i\cdot l_j$ be the number of sequences with $(a_4=i,a_5=j)$. Then: $$N_{1,1} = N_{8,8} = 13^2\\ N_{2,2} = N_{7,7} = 22^2\\ N_{3,3} = N_{6,6} = 26^2\\ N_{4,4} = N_{5,5} = N_{4,5} = N_{5,4}=27^2\\ N_{1,2} = N_{2,1} = N_{7,8} = N_{8,7}=13\cdot 22\\ N_{2,3} = N_{3,2} = N_{6,7} = N_{7,6}=22\cdot 26\\ N_{3,4} = N_{4,3} = N_{5,6} = N_{6,5}=26\cdot 27\\ $$
Our desired number is $$\sum_{1\leq i\leq j\leq 8}N_{i,j} = 11814.$$
I would greatly appreciate any comments, because I'm not very familiar with this kind of math-contest problems.
Edit: For anyone still interested, I checked this numerically in python and the result is in fact correct.