k pilas con $k(k+1)/2$ bolas

Question

Dado $\frac{k(k+1)}{2}$ bolas dispuestas en $m$ pilas.

Un jugador escoge una bola de cada pila y crea una nueva pila.

Como resultado, los pilotes con una bola de desaparecer, y una pila nueva con $m$ bolas es creado.

Por ejemplo, ( $k=2$ ), si ordenamos los pilotes por su tamaño: $$(1,1,1)\rightarrow (3) \rightarrow (1,2) \rightarrow (1,2)$$

Es fácil ver, que para cualquier $k$: $$(1,2,\dots,k)\rightarrow (1,2,\dots,k)$$

Deje $(1,2,\dots,k)$ se denota como el estado estacionario

Mostrar que no importa cuál sea la configuración inicial de pilas, las pilas de la configuración convergen en el estado estacionario.

Answer 1

Gracias al comentario por Miguel Lugo, encontré un papel que cubre el "búlgaro solitario" problema y la solución.

Yo sabía que la solución se basa en el establecimiento de una función que disminuye en cada movimiento, sin embargo, yo estaba teniendo problema viene con la función.

La función que el documento describe, es la energía potencial (altura veces los horarios de las misas g) de las bolas, cuando las pilas son verticales y se coloca en una caja, en el caso de que la caja se gira 45 grados.

Ver documento completo aquí

He probado la solución en python y funciona:

f = lambda x: sum([(len(x)-i)*t+(t+1)*t/2.0 for i,t in enumerate(x)])

Donde x es la ordenada de la tupla que se describe cuántas bolas hay en cada montón.

usted puede ver mi código completo aquí