Reconstrucción de un problema mensual: crecimiento del árbol en la red de enteros 2D

Question

Estoy tratando de reconstruir un problema que vi en el Monthly, hace años. Quizás a alguien le resulte familiar.

En el entramado de números enteros en el plano, hacemos crecer un árbol de la siguiente manera natural: Inicialmente el árbol es sólo el origen. En cada paso, encontramos el conjunto de puntos de la red que son vecinos (distancia 1) precisamente de un vértice de nuestro árbol, y los añadimos (simultáneamente) al árbol.

Así, en el día 0 el árbol es $\{(0,0)\}$ ; en el día 1 contiene $\{(0,0), (1,0), (-1,0),(0,1),(0,-1)\}$ el día 2 contiene esos vértices junto con $(2,0),(-2,0),(0,2)$ y $(0,-2)$ (nota que $(1,1)$ no se añade porque ya tiene dos vecinos en el árbol), y el día 3 añadimos 12 nuevos vértices. Parece un fractal bastante familiar.

Lo que no tengo claro es qué se le pidió exactamente a ese árbol... Los posibles candidatos incluyen su densidad asintótica, algún tipo de fórmula simple para determinar qué puntos de la red finalmente entran en el árbol y el número de vértices añadidos el día $n$ . Hay muchas preguntas interesantes y estoy encantado de intentar resolverlas, pero prefiero trabajar en las que realmente se han planteado.

Answer 1

Creo que lo tengo. Parece ser el problema 10360, publicado originalmente en 1994 (volumen 101, número 1, página 76), propuesto por Richard Stanley. Estoy mirando la página JSTOR de la solución (por Robin Chapman ), que apareció en octubre de 1998, volumen 105, nº 8, páginas 769-771).

Este es el planteamiento del problema:

Dejemos que $L$ sea el red de números enteros sur $\mathbb{R}^d$ es decir, el $L$ es el conjunto de puntos $(x_1,x_2,\ldots,x_d)$ con todos $x_j\in\mathbb{Z}$ . Considere $L$ como un gráfico declarando que dos puntos de la red son adyacentes si la distancia entre ellos es $1$ . Definir una secuencia $S_0$ , $S_1,\ldots$ de subconjuntos de $L$ inductivamente como sigue: \begin{align*} S_0 &= \Bigl\{ (0,0,\ldots,0)\Bigr\}\\\ S_{n} &= \Bigl\{ P\in L-\mathop{\cup}\limits_{0\leq k\lt n}S_k\ \Bigm|\ \text{$P$ is adjacent to exactly one element of $\mathop{\cup}\limits_{0\leq k\lt n}S_k$}\Bigr\}. \end{align*} Dejemos que $S$ sea el subgrafo de $L$ cuyos vértices son $\cup S_n$ . Así, $P\in S$ es adyacente a $P'\in S$ si la distancia entre $P$ y $P'$ es $1$ .

1. Encuentre una condición simple para un punto de $L$ para pertenecer a $S$ .
2. Para $P\in S$ encontrar una regla simple para determinar $i$ tal que $P\in S_i$ .
3. ¿Cuántos elementos hay en $S_i$ ?
4. Cuántos $P\in S_i$ son adyacentes a ningún punto de $S_{i+1}$ ?
5. Demuestra que $S$ es un árbol.
6. Investigar la densidad (de vértices) de $S$ sur $L$ y compararlo con la mayor densidad de un subconjunto de $L$ para el que el subgrafo inducido es un árbol.