# Put a mouse to the last cell

1. We have (n=12) cells $C_1, C_2 ,\dots, C_{12}$ which are initially empty.
2. 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.

3. 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.

-
I don't understand. No matter how many times you do P, all cells but $C_1$ are empty, and, since M is not allowed for $C_1$, you can never do $M$. All you can do is keep putting more and more mice into $C_1$. Are you sure you have the rules right? –  Gerry Myerson Aug 17 '12 at 12:34
You right. Don't know why I wrote this. Fixed. –  Mike Aug 17 '12 at 12:39
@Michael Hardy Thank you for fixing my english! –  Mike Aug 17 '12 at 18:40
One simple observation. If we have $n_k$ mice in cell $k$, we can compute score $S=\sum_{k} n_kk^2$. Each step will increase this score by 2. Also, the operations $M$ and $P$ commute, so an optimal strategy will have to be to apply $M$ to the highest cell possible if possible. We then have to prove that getting a mouse to cell $k$ will leave one mouse in each of cells $2,\ldots,k-2$, plus 1 or 2 in cell 1. (Not sure the score will be of use if following this latest strategy.) –  Einar Rødland Aug 17 '12 at 19:24

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.