7
$\begingroup$
  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.

  • 4
    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.)2012-08-17

1 Answers 1

4

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.

  • 0
    I am not sure that I am completly understand how this provides a minimal solution. But I believe that you are right and I need just some time. However, thank you.2012-08-18