Put a mouse to the last cell 
*

*We have (n=12) cells $C_1, C_2 ,\dots, C_{12}$ which are initially empty.

*At each step, we can do one of two operations:
$\mathbf{P}$: Put only in the first cell $C_1$ 2 mice.
$\mathbf{M}$: Move from any cell $C_k$ two mice. In this case, you have to put one mouse in $C_{k-1}$, and another mouse you have to put in $C_{k+1}$. $\mathbf{M}(C_1)$ means that we put one mouse in $C_2$ and remove another mouse from the field.

*Let F(n) is the number of steps, for which we put a mouse to the last cell $C_n$. Find the smallest F(n=12) - ?
It was the most difficult problem on our math competition. I solved it, and even found general formula for any number of cells and got all points for it. But i don't like how I did it.
First we can see, that if in every cells $C_2, C_3, \dots, C_k$  is already sitting at least one mouse, than we need only $k+1$ steps, to put a mouse to the cell $C_{k+1}$. After that, you will need to make a few steps $(m(k+1))$ to get a situation when in every cells $C_2, C_3, \dots, C_k, C_{k+1}$  is already sitting at least one mouse. And so on.
It is easy to find that if $n=4$ then $F(4)=11$. After that we can find that $m(5)=4$ so $F(5)=F(4)+4+5=20$. And this is how I found a recurrence formula $F(k)=F(k-1)+m(k)+k$. I didn't have time to find exact formula for $ m(k)$, I just calculated it for few first cases and then found the general formula. $m(6)=7, m(7)=12, m(8)=18, m(9)=24 \dots $ and so on.
$F(6)=33, F(7)=52, F(8)=78, F(9)=111, F(10)=152, F(11)=203$ and finally $F(12)=265$.
This give us:
$$
F(n)=\left[ \frac{n(n-1)}{4} \right] + \frac{n(n^2-3n+8)}{6}.
$$
It is a sequence A026038 from oeis.
My questions are:

1) Is there some simple way to find this formula? Not in my way. It is bad, I know.
2) How we can proof that this formula give us a smallest number? This algorithm was just my guess. I didn't prove that this algorithm provides a minimal solution.

Thank you for any help.
 A: Einar's "simple observation" in a comment goes a long way towards the solution.
The moves all commute as long as we don't move an $M$ move before the move that made it possible. Thus, given any sequence of moves, whenever a move creates a situation with at least two mice in at least one cell, we can find the next $M$ move for the highest such cell and reschedule it to make it the next move. There has to be such a move since we can't perform $M$ on any higher cells without first performing it on this one.
Thus rearranged, the sequence of moves will consist of runs of $M$ moves applied to successive cells: Whenever there are at least two mice in a cell, this "bulge" will propagate until it hits a cell with no mice in it. We can show by induction that these runs cause only the following transitions, where cells are numbered from left to right,   $(k)$ denotes a string of $k$ ones and $m,n\in\mathbb N_0$:
$$
\def\tr{\rightarrow}
\begin{array}l
0(n+1)&\tr&1(n)0(1)\\
1(m+1)0(n)&\tr&2(m)0(n+1)\\
2(m+1)0(n)&\tr&1(m)0(n+1)\\
10(n)&\tr&1(n+1)\\
20(n)&\tr&0(n+1)
\end{array}
$$
Only the first transition, or the second or third with $n=0$, reaches a new cell, so the state after reaching a new cell is always of the form $\{1|2\}(n)01$, where $\{1|2\}$ denotes either $1$ or $2$. Then Einar's score readily yields the number of moves required to reach that state, with the $1$ or $2$ being determined by the fact that the score is even.
