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