Poner un ratón hasta la última celda

Question

1. Tenemos (n=12) de las células $C_1, C_2 ,\dots, C_{12}$ cuales son inicialmente vacía.

2. En cada paso, podemos hacer una de dos operaciones:

   $\mathbf{P}$: Poner sólo en la primera celda $C_1$ 2 ratones.

   $\mathbf{M}$: Movimiento desde cualquier celular $C_k$ dos ratones. En este caso, usted tiene que poner un ratón en $C_{k-1}$, y otro ratón que tienes que poner en $C_{k+1}$. $\mathbf{M}(C_1)$ significa que vamos a poner un ratón en $C_2$ y quitar otro ratón de campo.

3. Sea F(n) es el número de pasos, para que nos ponga un ratón hasta la última celda $C_n$. Hallar el mínimo de F(n=12) - ?

Fue el problema más difícil en nuestra competencia de matemáticas. Lo resuelto, e incluso se encuentran la fórmula general para cualquier número de células y tiene todos los puntos para ello. Pero no me gusta cómo lo hice yo.

Primero podemos ver que si en cada una de las células de la $C_2, C_3, \dots, C_k$ ya está sentado en menos de un ratón, que sólo necesitamos $k+1$ pasos, para poner un ratón a la celda $C_{k+1}$. Después de eso, usted tendrá que hacer un par de pasos $(m(k+1))$ a una situación cuando en cada una de las células de la $C_2, C_3, \dots, C_k, C_{k+1}$ ya está sentado en menos de un ratón. Y así sucesivamente.

Es fácil encontrar que si $n=4$$F(4)=11$. Después de que nos podemos encontrar en que $m(5)=4$$F(5)=F(4)+4+5=20$. Y así es como he encontrado una fórmula de recurrencia $F(k)=F(k-1)+m(k)+k$. No tuve tiempo para encontrar la fórmula exacta para $ m(k)$, yo sólo calcula que por unos primeros casos y, a continuación, encontrar la fórmula general. $m(6)=7, m(7)=12, m(8)=18, m(9)=24 \dots $ y así sucesivamente. $F(6)=33, F(7)=52, F(8)=78, F(9)=111, F(10)=152, F(11)=203$ y, finalmente,$F(12)=265$.

Esto nos da:

$$ F(n)=\left[ \frac{n(n-1)}{4} \right] + \frac{n(n^2-3n+8)}{6}. $$

Es una secuencia de A026038 de oeis.

Mis preguntas son:

1) ¿hay alguna manera sencilla de encontrar esta fórmula? No en mi camino. Es malo, lo sé.

2) ¿Cómo podemos prueba de que esta fórmula nos da un número más pequeño? Este algoritmo fue sólo mi suposición. Yo no demostrar que este algoritmo proporciona una solución mínima.

Gracias por cualquier ayuda.

Answer 1

Einar "simple observación" en un comentario va un largo camino hacia la solución.

Los movimientos de todos los conmutar mientras no nos movemos de una $M$ moverse antes de que el movimiento que la hizo posible. Así, dada una secuencia de movimientos, cada vez que un movimiento crea una situación en la que, al menos, dos ratones en al menos una celda, podemos encontrar la siguiente $M$ moverse por la más elevada de la celda y volver a programarlo para hacer el siguiente movimiento. Tiene que haber un movimiento como tal ya que no se puede realizar la $M$ superior de las células sin realizar primero en algo.

Por lo tanto reorganizar la secuencia de movimientos que constará de las carreras de la $M$ movimientos aplicados a las sucesivas células: Siempre hay al menos dos ratones en una celda, este "bulto" se propagará hasta que llega a una celda sin ratones. Podemos demostrar por inducción que estas carreras causa sólo el seguimiento de las transiciones, donde las células están numerados de izquierda a derecha, $(k)$ denota una cadena de $k$ queridos y $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} $$

Sólo la primera transición, o la segunda o la tercera con $n=0$, alcanza un nuevo celular, por lo que el estado después de llegar a una nueva célula es siempre de la forma $\{1|2\}(n)01$ donde $\{1|2\}$ denota cualquiera de las $1$ o $2$. A continuación, Einar la puntuación fácilmente se obtiene el número de movimientos necesarios para llegar a ese estado, con la $1$ o $2$ está determinado por el hecho de que la puntuación es aún.