Solitario búlgaro: Tamaño de los bucles de raíz

Question

Conocí el solitario búlgaro por uno de los libros de Martin Gardner hace tiempo y desde entonces lo he investigado un poco. La búsqueda en Google ha revelado que se ha trabajado sorprendentemente poco (públicamente al menos) en esta área.

El juego funciona de la siguiente manera: coge un número cualquiera de objetos (como monedas o piedras pequeñas) y divídelos en un número cualquiera de pilas con un número cualquiera de objetos en cada pila. A continuación, coge un objeto de cada montón y crea un nuevo montón con ellos. Repite la operación durante el tiempo que sea necesario. Por ejemplo:

$10$ artículos, empezando por montones de $4, 4, 1, 1$

Al principio, hay cuatro montones. Tomando un elemento de cada uno nos queda $3, 3$ . Sumando los cuatro que tomamos nos da $4, 3, 3$ . Repitiendo este paso se consigue...

$4, 4, 1, 1$
$4, 3, 3$
$3, 3, 2, 2$
$4, 2, 2, 1, 1$
$5, 3, 1, 1$
$4, 4, 2$
$3, 3, 3, 1$
$4, 2, 2, 2$
$4, 3, 1, 1, 1$
$5, 3, 2$
$4, 3, 2, 1$
$\mathbf{4, 3, 2, 1}$
$\dots$

Los que tengan buen ojo verán rápidamente que $4, 3, 2, 1$ es un estado estable en el sentido de que pasar un turno del juego no cambia nada. Lo que es más interesante es que CADA configuración inicial de $10$ los artículos terminarán en este estado estable. Además, $6$ los artículos siempre acabarán en $3, 2, 1$ ; $15$ los artículos siempre acabarán en $5, 4, 3, 2, 1$ y así sucesivamente. Los números triangulares de elementos son los únicos para los que ocurre esto. Esto se debe a que sólo un $n, n-1, n-2, \dots, 3, 2, 1 { }$ estado es estable; restando uno a cada uno se elimina el $1$ -pila y añade una pila de $n$ . Evidentemente, un número triangular de elementos da lugar a un "bucle raíz" de tamaño 1.

Voy a exponer una observación y un hecho que se desprende de ella. Esta observación es que todas las particiones de $n$ llevará exactamente a otra partición de $n$ por definición. Esto significa que, aunque pueden existir bucles, nunca puede haber una partición de $n$ que lleva a dos particiones de $n$ . Esto tiene el efecto de dividir un grafo dirigido (una arista de $i$ a $j$ tiene peso 1 si la partición $i$ lleva a la partición $j$ ) en un número de subgrafos que corresponde exactamente al número de bucles. Esto no es difícil de demostrar, y yo no soy Fermat. :P

Lo que me pareció aún más interesante fue lo que ocurrió cuando se utilizó un número no triangular de elementos. En estos casos, se entra en un bucle. Por ejemplo...

$7$
$6, 1$
$5, 2$
$4, 2, 1$
$3, 3, 1$
$3, 2, 2$
$3, 2, 1, 1$
$\mathbf{4, 2, 1}$
$\dots$

Así, a partir de $7$ termina en un bucle raíz de tamaño $4$ . Más experimentos revelan que dado un número no triangular $n$ de elementos, hallar el número triangular $T_k \geq n$ y $k$ es el tamaño de al menos uno de los bucles raíz en el grafo dirigido de todas las particiones de $n$ .

Why is this so?

Answer 1

Probablemente esto se trate en uno de los documentos que aparecen en la búsqueda de Gerry, pero ya que le dediqué un poco de tiempo voy a publicar una solución de todos modos. La solución también es relativamente corta.

La conjetura de El'endia es correcta. Un ciclo de la longitud prescrita puede construirse como sigue. Primero recordamos la partición del punto fijo $p_k=(k,k-1,k-2,\ldots,2,1)$ del número del triángulo $n=T_k=k(k+1)/2$ . Supongamos que, en cambio, el número total de piedras es $n=k(k+1)/2-m$ , donde $0<m<k$ . Afirmo que en este caso obtenemos un ciclo de longitud $k$ quitando una piedra del $m$ pilas más pequeñas de la partición $p_k$ . En otras palabras, estudiemos la partición $$p_k^*=(k,k-1,k-2,\ldots,m+1,m^*,(m-1)^*,...,2^*,1^*),$$ donde utilizo la graciosa notación $\ell^*$ para denotar una pila de $\ell-1$ piedras, porque ese montón realmente quiere tener $\ell$ piedras, pero se siente un poco dejado de lado. Por lo tanto, $1^*$ realmente es una pila vacía.

Dejemos que $p_k^{*,m,i}$ denotan la partición obtenida de $p_k$ por el marcado $m$ entradas consecutivas a partir del $i$ -pilar con un asterisco. Si $i<m$ y luego movemos los asteriscos restantes al principio de la partición de la forma cíclica habitual (por lo que la partición anterior $p_k^{*}=p_k^{*,m,m}$ ). Por ejemplo, $$p_5^{*,3,2}=(5^*,4,3,2^*,1^*)=(4,4,3,1,0)=(4,4,3,1).$$ La observación clave es que el movimiento del solitario búlgaro mapea la partición $p_k^{*,m,i}$ a la partición $p_k^{*,m,i-1}$ , donde interpretamos $i-1=0$ como $k$ (o disminución $i$ por un módulo $k$ ). Esto es fácil de ver, porque las entradas de todas estas particiones están en orden descendente. Lo único ligeramente complicado es que la pila vacía $1^*$ corresponde a $k^*$ después de la jugada del solitario búlgaro, porque la presencia de una pila vacía significa que la nueva pila pierde una de sus piedras, y obtiene sólo $k^*$ piedras en lugar de las habituales $k$ .

A modo de ejemplo, dejemos que $n=25=28-3=T_7-3$ . Entonces obtenemos un ciclo de 7 particiones empezando por $(7,6,5,4,3^*,2^*,1^*)=(7,6,5,4,2,1)$ . El ciclo se compone de las particiones $$(7^*,6,5,4,3,2^*,1^*)=(6,6,5,4,3,1),$$ $$(7^*,6^*,5,4,3,2,1^*)=(6,5,5,4,3,2),$$ $$(7^*,6^*,5^*,4,3,2,1)=(6,5,4,4,3,2,1),$$ $$(7,6^*,5^*,4^*,3,2,1)=(7,5,4,3,3,2,1),$$ $$(7,6,5^*,4^*,3^*,2,1)=(7,6,4,3,2,2,1),$$ $$(7,6,5,4^*,3^*,2^*,1)=(7,6,5,3,2,1,1),$$ y de vuelta a $$(7,6,5,4,3^*,2^*,1^*)=(7,6,5,4,2,1).$$

Answer 2

Hace varios años, escribimos un artículo que explica la dinámica del solitario búlgaro con un número no triangular de las piedras. Resulta que se pueden tener bucles de raíz de varios tamaños diferentes, pero sus longitudes dependen del número triangular más pequeño $T_k$ con $T_k \geq n$ . En particular, la longitud de todos los bucles siempre dividirá $k$ y siempre habrá al menos uno de longitud $k$ (a menos que $n=T_k$ ). Para una exposición más completa, puede encontrar nuestro papel aquí .