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.

  • $\begingroup$ 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? $\endgroup$ – Gerry Myerson Aug 17 '12 at 12:34
  • $\begingroup$ You right. Don't know why I wrote this. Fixed. $\endgroup$ – Mike Aug 17 '12 at 12:39
  • $\begingroup$ @Michael Hardy Thank you for fixing my english! $\endgroup$ – Mike Aug 17 '12 at 18:40
  • 4
    $\begingroup$ 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.) $\endgroup$ – Einar Rødland Aug 17 '12 at 19:24

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.

  • $\begingroup$ 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. $\endgroup$ – Mike Aug 18 '12 at 9:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.