Un juego de piedras

Question

Cómo llegué a esta pregunta es un poco largo de la historia tienen que ver con los honores clase de cálculo estoy enseñando. En este punto es pura curiosidad de mi parte. Aquí está el juego.

$\newcommand{\bZ}{\mathbb{Z}}$

Empezamos con una colección finita de piedras colocadas al azar en algún lugar en el conjunto de nodos $\newcommand{\eN}{\mathscr{N}}$ $$\eN=\{2,3,4,\dotsc\}. $$ We can view a distribution of stones as a function $s:\eN\to\bZ_{\geq 0} $ with finite support, $s(n)=$ the number of stones at $$ n. Su peso es el número entero no negativo

$$|s|=\sum_{n\in\eN} s(n). $$

Se dice que una distribución $s$ es de hacinamiento si $s(n)> 1$ para algunos $n\in\eN$. Un nodo $n$ se llama ocupados (con respecto a $s$) si hay al menos una piedra en $n$, $s(n)>0$.

Nos permite los movimientos siguientes: elegir un ocupados nodo $n$. A continuación, mueva una piedra de la ubicación de $n$ a de la ubicación de $n+1$ y añadir una nueva piedra en la ubicación de $n^2$. Tenga en cuenta que tal medida que aumenta el peso por $1$.

Ahora viene la pregunta.

Es cierto que para cualquier distribución inicial de piedras $s:\eN\to\bZ_{\geq 0}$ y cualquier entero positivo $N$ existe una secuencia finita de vanos se mueve de manera tal que después de estos movimientos se obtiene una nueva distribución de las piedras que (i) es no hacinamiento, y (ii) ningún nodo $n<N$ se encuentra ocupado.

La evidencia empírica me lleva a creer que la respuesta a esta pregunta es positiva. Sin embargo, no he logrado encontrar un argumento concluyente.Estoy esperando que alguien en el MO comunidad tendrá más suerte.

Comentario 1. (Inspirado por David Eppstein la respuesta.) Quiero demostrar que si la función de $n\mapsto n^2$ en la definición de un margen de movimiento es reemplazado por algo más que la respuesta a la pregunta puede ser negativo. En otras palabras, ninguna prueba de la respuesta positiva, habría que tener en cuenta algunas características del mapa $n\mapsto n^2$.

Aquí está el ejemplo. Fijar un número entero $k>1$ y definir $f:\eN\to\eN$, $f(n)=n+k$. Ahora cambiar la definición de un margen de mover de la siguiente manera.

Escoge un ocupados nodo $m$. Mover una piedra de la ubicación de $m$ a $m+1$ y añadir una piedra en el nodo $f(m)$. Vamos a denotar por $T_m$ este movimiento.

Deje $s_0:\eN\to\bZ_{\geq 0}$ ser la configuración que consta de una sola piedra que se encuentra en $n=2$. Me dicen que no existe $N>0$ tal que $s_0$ no puede ser movido más allá de $N$ sin hacinamiento.

La prueba se basa en una ley de la conservación de lo sugerido por David Eppstein la respuesta. Considere el polinomio $P(x)=x^k+x-1$. Tenga en cuenta que $P(0)<0$ e $P(1)>0$ lo $P$ tiene al menos una raíz en el intervalo de $(0,1)$. Elegir uno de estos raíz de $\rho$. Utilizamos $\rho$ a definir la energía de una configuración de $s:\eN\to\bZ_{\geq 0}$ a

$$ E(s):=\sum_{n\in \eN} s(n)\rho^n. $$

Si $m$ es ocupado ubicación de una configuración de $s:\eN\to\bZ_{\geq 0}$, luego

$$E(T_m s)= E(s)-\rho^m+\rho^{m+1}+\rho^{m+k}=E(s)+\rho^mP(\rho)=E(s). $$

Por lo tanto admisible se mueve no cambiar la energía de una configuración.

Deje $N$ ser un entero positivo tal que

$$\rho^{N-2}<1-\rho. \tag{1} $$

Supongamos ahora que el uso permitido mover podemos transformar $s_0$ a una configuración de $s$ tal que

$$ s(n)=0,\;\;\forall n<N,\;\;s(n)\in \{0,1\},\;\;\forall n\geq N. $$

Entonces

$$\rho^2= E(s_0)=E(s)\leq \sum_{n\geq N}\rho^n=\frac{\rho^N}{1-\rho}. $$

Esta última desigualdad viola el supuesto (1), lo que confirma mi afirmación.

Observación 2. El ejemplo en el anterior comentario tiene las siguientes evidente la generalización. Supongamos que $f:\eN\to\eN$ es una función tal que $f(n)>n+1$, $\forall n \in \eN$ y existe una probabilidad de medida $\pi$ a $\eN$ tal que

$$ \pi\bigl(\; f(n)\;\bigr)+\pi(n+1)-\pi(n)\geq 0,\;\;\forall n\in\eN. \tag{2}$$

El uso de $f$ para definir el margen de movimientos, uno puede demostrar que no existe $N>0$ tal que $s_0$ no puede ser movido más allá de $N$ sin hacinamiento. La prueba utiliza la entropía

$$E_\pi(s)=\sum_{n\in\eN}s(n)\pi(n). $$

Tenga en cuenta que esta entropía es, precisamente, la expectativa de $s$ con respecto a la probabilidad de medida $\pi$, y no disminuye a medida que aplicamos permitido mueve

$$E(s)\leq E(T_m s), \;\;\forall s. $$

Para $f(n)=n+k$ podemos definir

$$ \pi(n)=(1-\rho)\rho^{n-2}. $$

Esta observación plantea la siguiente pregunta natural.

Encontrar las funciones $f:\eN\to \eN$ tal que $f(n)>n+1$, $\forall n\in \eN$, y existe una probabilidad de medida $\pi$ a $\eN$ satisfactorio (2). Cómo de rápido puede una función crecer como $n\to \infty$?

Observación 3. (a) Por $f(n)=n^2$ la condición (2) se lee

$$ \pi(n^2)+\pi(n+1)\geq \pi(n). \tag{3} $$

Uno puede mostrar que una serie $$\sum_{n\geq 1}p(n) $$ with nonnegative terms satisfying (3) is divergent if not all the terms are trivial. (This was the rather tricky honors calculus problem that prompted the present question.) Hence, for the function $f(n)=n^2$, no existe probabilidad de medidas de satisfacción (2), lo que sugiere indirectamente que la pregunta original podría tener una respuesta positiva.

(b) Si $f(n)=n +1+ \lfloor \sqrt{n}\rfloor$, $\alpha>1$ es lo suficientemente cerca de a $1$ y

$$\pi(n)=\frac{C}{n^\alpha}, \;\;C\sum_{n\geq 2}\frac{1}{n^\alpha}=1,$$

entonces la condición (2) se cumple para moverse sin hacinamiento no es posible si la capacidad se mueve utilizar la función $f(n)$.

Observación 4. Eche un vistazo a Michael Stoll excelente respuesta.

Answer 1

Algo muy similar a esto ya se sabe. Si tus movimientos son para reemplazar una concurrida de piedra en $n$ con dos piedras en $n+1$ e $n(n+1)$, entonces estos movimientos preservar el valor de $\sum_n s(n)/n$, y en una poca gente configuración de esta suma es un Egipcio fracción (una suma de un número finito de distintas fracciones de unidades). El algoritmo que se aplica repetidamente estos movimientos (el orden no importa) hasta que todo esté poca gente se llama el método de división de fracciones Egipcias. Su eventual terminación fue probada por

L. Beeckmans. El algoritmo para la división de fracciones Egipcias. J. Número De Th. 43, 1993, pp 173-185.

También hay una descripción de la misma forma, con su terminación atribuido a Graham y Jewett, en

S. Wagon. Mathematica en Acción. W. H. Freeman, 1991, pp 271-277.

Pero no tengo el original de Graham–Jewett referencia a la mano.

Answer 2

$\newcommand{\bZ}{\mathbb{Z}}$ $\newcommand{\eN}{\mathscr{N}}$

Aquí es una prueba de que no tratar el hacinamiento como un caso especial. Como se observó en algunos comentarios, es realmente suficiente para probar el resultado deseado para el caso de una piedra. La realidad de las pruebas ocupa menos espacio que las declaraciones y todos los de la notación. Voy a

• repetir el resultado deseado como un teorema en un equivalente pero un poco más detallada de la manera de ayudar a la prueba.
• reclamación de un resultado, lo que implica el teorema para el caso de una piedra
• demostrar el teorema de
• Demostrar que la prueba de la reclamación proporciona un mayor resultado.

Voy a encontrar conveniente pensar en la $s$ como un conjunto múltiple (aunque voy a utilizar la piedra de idioma también). Voy a pensar en un movimiento como la extracción de una piedra y reemplazarlo con dos hijos. La mayoría del tiempo voy a estar tratando de demostrar que $s$ es en realidad un conjunto.

TEOREMA: Para cualquier distribución inicial de piedras $s:\eN\to\bZ_{\geq 0}$ con $2 \le p =\max{s}$ y cualquier entero positivo $N$ existe un entero $M=M(s,N)$ y una secuencia de movimientos después de lo cual se obtiene una nueva distribución de las piedras que (i) es un conjunto (no hay dos piedras ocupan el mismo lugar), (ii) no tiene ningún nodo $n<N+p$ ocupado y (iii) no tiene ningún nodo $n>M$ ocupado.

---

RECLAMO: Considere la posibilidad de una configuración inicial $s(0)=\{{q+1\}}$ consta de una sola piedra en la posición $q+1 \ge 2$. Deje $$s(1)=\{{q+2,(q+1)^2\}}$$ $$s(2)=\{{q+3,(q+2)^2,(q+1)^2+1,(q+1)^4\}}$$ and in general $$s(k)=\{{x+1 \mid x \in s(k-1)\}} \cup \{{x^2 \mid x \in s(k-1)\}}.$$ So $s(k)$ is a multiset with $2^k$ elements, the smallest being $q+k+1$ and the largest $(q+1)^{2^k}.$ Then $s(k)$ es, de hecho, un conjunto.

Supongamos que ya sabemos el $s(j)$ se establece para todos los $j \lt k.$ queremos mostrar que $s(k)$ no tiene elementos repetidos. Un número $v \in s(k)$ que no es un cuadrado que sólo puede surgir como $(v-1)+1$ para $v-1 \in s(k-1).$ valor $v \lt (q+1)^2$, plaza o no, sólo puede ser $v=q+k+1.$ queda por considerar el cuadrado de los valores de $u^2 \in s(k)$ con $u \ge (q+1)^2.$ Si $u^2-1 \notin s(k-1)$, entonces sabemos $u \in s(k-1)$ e $u \ge q+k=\min(s(k-1)).$ ahora veremos que, independiente de la $q$, si $u^2-1 \in s(k-1)$ entonces $u \le\frac{k+1}{2}$ lo $u \notin s(k-1).$ Si $u^2-1 \in s(k-1)$, a continuación, también se $u^2-2\in s(k-2)$, y así hasta la plaza anterior $u^2-2u-1 \in s(k-2u+1).$, Pero esto significa $0 \le k-2u+1$ lo $ u \le \frac{k+1}{2}$

Esto establece el teorema para un singleton set $s=\{{p\}}$ con $M(s,N) \le p^{2^{N+1}}.$

---

La PRUEBA DEL TEOREMA: La prueba es por inducción sobre el número de piedras presente. El caso de una piedra es la afirmación anterior con $M = p^{2^{N+1}}$. Si hay más de una piedra, vamos a $s'$ ser la posición obtenida por la reducción del número de piedras en el último cargo ocupado por $1$. A continuación, utilice el reclamo para mover una sola piedra desde esa posición y mantenerse en movimiento la descendencia hasta que todos los resultantes de las piedras se mueven pasado $M(s',N).$, Entonces, por hipótesis, se puede redistribuir el (descendencia) de las piedras de $s'$ sin chocar con alguno de los descendientes de la primera piedra.

Como consecuencia, si $s$ tiene al menos dos piedras y $p$ es el más grande lleno de posición de $s$,, a continuación, $M(s,n) \le M(\{{p\}},M(s',N)) \le p^{2^{M(s',N)+1}}.$ El fuerte reclamo a continuación permitiría a los más pequeños, pero aún enorme, límites superior.

---

Tenga en cuenta que la configuración de $\{{p,p^2-1\}}$ lleva inmediatamente a la colisión si el movimiento se aplica tanto a los miembros. Voy a demostrar que para una más grande, pero un poco más delgada, la configuración no colisiones se producen incluso con múltiples iteraciones.

FUERTE RECLAMO: Consideremos, por $q+1 \ge 2,$ una configuración inicial $s(0)=\{{q+1,q+2,\cdots , (q+1)^2-2\}}.$ Para $k \gt 0$ vamos $$s(k)=\{{x+1 \mid x \in s(k-1)\}} \cup \{{x^2 \mid x \in s(k-1)\}}.$$ So $s(k)$ is a multiset with $2^k(p^2+q-1)$ elements, the smallest being $q+k+1$ and the largest $\left((q+1)^2-2\right)^{2^k}.$ Then $s(k)$ es, de hecho, un conjunto.

Está claro que $s(0)$ e $s(1)$ son conjuntos, se Asume que el $1 \lt k$ y ya sabemos la $s(j)$ se establece para todos los $j \lt k.$ queremos mostrar que $s(k)$ no tiene elementos repetidos. Un número $v \in s(k)$ que no es un cuadrado que sólo puede surgir como $(v-1)+1$ para $v-1 \in s(k-1).$ valor $v \le (q+1)^2$, plaza o no, sólo puede haber surgido de $v-k \in s(0)$ sin cuadrar. Queda por considerar el cuadrado de los valores de $u^2 \in s(k)$ con $u \gt (q+1)^2.$ Si $u^2-1 \notin s(k-1)$, entonces sabemos $u \in s(k-1)$ e $u \ge q+k = \min(s(k-1)).$ ahora veremos que, independiente de la $q$ si $u^2-1 \in s(k-1)$ entonces $u \le\frac{k+1}{2}$ lo $u \notin s(k-1).$ Si $u^2-1 \in s(k-1)$, a continuación, también se $u^2-2\in s(k-2)$, y así hasta la plaza anterior $u^2-2u-1 \in s(k-2u+1).$, Pero esto significa $0 \le k-2u+1$ lo $ u \le \frac{k+1}{2}.$

Answer 3

EDIT: La prueba a continuación tiene una brecha, ver los comentarios.

Voy a reformular las observaciones a continuación como algunas reducciones del problema en su lugar.

• Nos podemos en un número finito de pasos, asegúrese de que la primera $N$ nodos están vacíos. Por lo tanto, sigue siendo para resolver el problema del hacinamiento de los nodos.
• Deje $n$ ser un nodo, de tal manera que todos los nodos a la derecha de $n$ no son de hacinamiento. Si podemos demostrar que siempre es posible aumentar la longitud de la carrera con nodos vacíos a la derecha de $n$, sin introducir ninguna hacinamiento de los nodos a la derecha de $n$, hemos terminado. Por qué? Desde entonces, se puede considerar que la situada más a la derecha de hacinamiento nodo $n$, aumentar el vacío de ejecutar a un tamaño suficiente, y, a continuación, aplicar un movimiento en el sitio de $n$, por lo que se garantiza estrictamente disminuir el hacinamiento.
• Es suficiente para ser capaz de resolver el caso con una concurrida nodo (con dos piedras), y algunos no los lleno de gente nodos a la derecha de este nodo.

Aquí está la prueba incompleta

Como se ha señalado, siempre podemos escoger el más pequeño de los ocupados sitio, y en repetidas ocasiones se aplican al mover hasta que este está vacío. Por lo tanto, la segunda condición se puede tomar fácilmente la atención de primera, así que sólo tiene que preocuparse de overcrowdness.

Primero hacemos inducción sobre el número de atestado nodos.

Principales hipótesis: Supongamos que podemos solucionar hacinamiento de $\leq k$ hacinamiento nodos (con multiplicidad).

Considerar el más grande lleno de gente nodo $n$. Crear una lo suficientemente grande gap (ver más abajo) a la derecha de este nodo, de tal manera que podemos aplicar un movimiento en $n$, y estar seguro de que esto reduce el hacinamiento.

Por lo tanto, es suficiente para demostrar el siguiente lema:

Lema: Para cualquier nodo $n$ sin hacinamiento nodos, a su derecha, podemos crear una arbitraria gran brecha de desocupados sitios a la derecha de $n$, y de tal manera que no hay nodos a la derecha de $n$ son de hacinamiento.

Está claro que es suficiente para mostrar que podemos aumentar la brecha por 1. Ahora hacemos inducción sobre el número de piedras a la derecha de $n$. Supongamos que hemos hecho esto para $j$ piedras (una piedra es trivial, basta con aplicar el movimiento a la piedra), y que no se $j$ piedras a la derecha de $n$.

Considere la posibilidad de la piedra que está en el extremo izquierdo del nodo $m$ a la derecha de $n$. No menos de $j$ piedras a la derecha de $m$, por lo que por hipótesis de inducción, podemos hacer una gran piedra libre espacio a la derecha de $m$. Después de eso, podemos aplicar el movimiento en $m$ sin la introducción de nuevos sitios de hacinamiento y aumentando así el espacio a la derecha de $n$ por uno.

Answer 4

Esto no responde a la pregunta original, pero explora una versión más general.

Deje $\mathcal N = \{n_0,n_0+1,n_0+2.\ldots\}$ para algunos fijos $n_0 \in \mathbb Z$. Deje $f \colon {\mathcal N} \to {\mathcal N}$ ser un mapa tal que $f(n) > n$ para todos los $n \in \mathcal N$. Consideramos el juego con piedras en la $\mathcal N$, en un movimiento legal reemplaza una piedra en la posición $n$ con dos piedras en $n+1$ e $f(n)$. Digamos que $f$ es buena si por cualquier finito de configuración de piedras y cualquier $N \in \mathcal N$ hay una secuencia de movimientos legales que la transforma en una que no es de hacinamiento y no ocupa una posición $n < N$. Decimos que $f$ es malo lo contrario. La pregunta original era si $f(n) = n^2$ es buena y fue contestada positivamente por Aaron Meyerowitz. La cuestión que quiero tratar aquí es

Pregunta.
Donde (en términos de comportamiento del crecimiento de $f$) es la "fase de transición" entre el mal y el bien?

Voy a argumentar que este es un crecimiento de un comportamiento como $f(n) \sim n^2/2$.

Para esto, voy a combinar la entropía enfoque mencionado en el OP del Discurso y la idea de la prueba de Aarón respuesta.

Lema 1.
Supongamos que existe una discreta medida $\mu$ a $\mathcal N$ tal que
(i) $0 < \mu(\mathcal N) < \infty$ y
(ii) para todo lo suficientemente grande $n \in \mathcal N$, $\mu(\{n+1,f(n)\}) \ge \mu(\{n\})$.
A continuación, $f$ es mala.

Prueba. Para una configuración de la $s$ definimos $\mu(s) = \sum_{n \in \mathcal N} s(n)\mu(\{n\})$. Deje $n' \in \mathcal N$ satisfacer $\mu(\{n'\}) > 0$, y estar lo suficientemente grande como para que (ii) se aplica a todos los $n \ge n'$. Considere la posibilidad de una configuración de $s$ de % de $m$ piedras en $n'$ donde $\mu(s) = m \mu(\{n'\}) > \mu(\mathcal N)$. Luego, por (ii) cualquier secuencia de movimientos legales que conduce a una configuración de $s'$ con $\mu(s') \ge \mu(s) > \mu(\mathcal N)$, mientras que los no-hacinamiento posición $s''$ ha $\mu(s'') \le \mu(\mathcal N)$. Así que, de hecho ninguna posición en la que nos pueden llegar por los movimientos legales de $s$ evita el hacinamiento. $\Box$

Lema 2.
Se supone que hay una constante $C$ tal que $f(n+1) + C \ge f(n) + n$ para todos lo suficientemente grande $n \in \mathcal N$.
A continuación, $f$ es bueno.

Prueba. Fix $q \in \mathcal N$ tal que $q > C+2$ y la condición en $f$ mantiene para $n \ge q$. Deje $s_0$ ser la posición que consiste en una piedra en $q$. Dejamos $s_{m+1}$ ser la posición obtenida de $s_m$ aplicando el movimiento legal de cada piedra en $s_m$. Me reclama que no $s_m$ es de hacinamiento. Esto es especialmente cierto para $m = 0$. Asumir la afirmación es falsa y deje $m \ge 0$ ser el más pequeño $m$ tal que $s_{m+1}$ es de hacinamiento. Luego hay $n_1, n_2 \in s_m$ tal que $n_1+1 = f(n_2)$. Hay dos posibilidades. Cualquiera de las $n_1 = q+m$; a continuación, $n_1$ es el más pequeño ocupado su lugar en $s_m$ y la contradicción $n_1+1 = f(n_2) > n_2 + 1 \ge n_1 + 1$ (utilizamos $n_2 \ge q > C+1$ aquí). O obtenemos $n_1$ de $q$ por una secuencia de pasos $n \mapsto n+1$ e $n \mapsto f(n)$ que contiene al menos una solicitud de $f$. En este caso, al menos la última $f(n_2) - f(n_2-1) - 1 \ge n_2 - (2+C)$ pasos deben ser $n \mapsto n+1$ (ya que no hay ningún valor de $f$ entre $f(n_2-1)$ e $f(n_2)$). Por lo $m \ge n_2 - (2+C)$. Por otro lado, $n_2 \ge q + m$, con lo que obtenemos una contradicción de nuevo, ya que $q > C+2$.

Esto muestra la definición de propiedad para el bien $f$ para una sola piedra posiciones en los lugares $> C+2$. Ya se ha observado en este hilo que esto es suficiente para establecer que $f$ es bueno. $\Box$

Teorema.
(1) Si $\limsup_{n \to \infty} \dfrac{f(n)}{n^2} < \frac{1}{2}$,, a continuación, $f$ es mala.
(2) Si $\liminf_{n \to \infty} \bigl(f(n+1)-f(n)-n\bigr) > -\infty$,, a continuación, $f$ es bueno. En particular, si $f(n) = n^2/2 + k n + O(1)$ para algunos $k \in \mathbb R$,, a continuación, $f$ es bueno.

Prueba. La parte (2) se sigue inmediatamente de Lema 2. Para la parte (1), fix $\alpha > 1$ tal que $2^{-\alpha} > \beta = \limsup f(n)/n^2$ y considere la posibilidad de una medida $\mu$ dado por $\mu(\{n\}) = (n (\log n)^\alpha)^{-1}$ para $n \gg 0$. A continuación, $\mu(\mathcal N)$ es finito. También, $$ \mu(\{n\}) - \mu(\{n+1\}) \sim \frac{1}{n^2 (\log n)^\alpha} ,$$ que crece más lentamente que $$ \mu(\{f(n)\}) \ge \frac{1}{\beta 2^\alpha n^2 (\log n)^\alpha}(1 + o(1)), $$ así que la hipótesis del Lema 1 se satisfacen. $\Box$

Corolario.
Si $f$ es un polinomio, entonces $f + O(1)$ es buena si y sólo si $\deg f \ge 3$ o $\deg f = 2$ y el coeficiente inicial de $f$ es $\ge 1/2$.