Problema de ordenación de la combinatoria

Question

Esta es una pregunta de combinatoria:

1. Imagina que tienes un $8\times8$ tablero de ajedrez vacío.

2. Usted tiene $10$ peones idénticos.

3. ¿De cuántas formas diferentes puedes colocar esos $10$ peones en el tablero de ajedrez de manera que cada peón esté a una distancia (euclidiana) mínima $X$ ¿se aleja de alguno de los otros peones?

4. Esto es sólo un ejemplo, pero lo que me gustaría es una función a la que le pueda dar las dimensiones del tablero de ajedrez, el número de peones que debe haber en el tablero, y la distancia mínima a la que debe estar cada peón de cualquiera de los otros peones, y entonces la función devuelve el número de disposiciones posibles.

5. Si no sabe cómo resolver este problema, ¿podría indicarme qué subcampo de la combinatoria puedo aprender para resolver este problema? Por ejemplo, ¿hay alguna forma inteligente de utilizar la inclusión-exclusión para resolver este problema?

6. Por último, si el problema anterior es demasiado difícil, ¿cómo lo harías si en lugar de un tablero de ajedrez que es $8\times 8$ , tenías una tabla larga que era $64\times 1$ ?

Gracias.

Answer 1

Para el problema lineal (en $p\times1$ ), esto es relativamente fácil. Pongo un ejemplo: tienes 4 peones que deben estar a distancia 8 (los peones adyacentes están a distancia 1) en una $30\times 1$ tablero. Así, el primer peón puede estar en la casilla 1, el segundo en la 9, el tercero en la 17 y el último en la 25. Esta es la solución más a la derecha, por lo que el último peón sólo puede estar en la celda $p_{4}$ con $25\le p_4 \le 30$ .

Una vez que haya fijado $p_4$ , entonces se puede verificar que $p_1=1+a_1$ , $p_2=p_1+8+a_2$ , $p_3=p_2+8+a_3$ y $p_4=p_8+8+a_4$ con $a_1+a_2+a_3+a_4=p_4-25$ (y $a_i\ge 0$ ). ¿Cuántos diferentes $a_i$ ¿verificar esto? $\binom{p_4-25+3}{3}$ .

Así que el número que quieres encontrar sería : $\sum_{p=25}^{30}\binom{p-25+3}{3}$ = $\sum_{p=0}^{5}\binom{p+3}{3}$ .

Por 10 peones en un $64\times 1$ carril, con la distancia $1\le X\le 7$ , sería $$\sum_{p=0}^{63-9X}\binom{p+9}{9}=1+10+55+220+\dots$$ .

En un tablero bidimensional, esto es (creo) una cuestión abierta, incluso para $X=2$ . Por ejemplo la entropía cuadrada dura es un problema cuando queremos saber de cuántas maneras se pueden poner peones en un tablero cuadrado con $X=2$ (puedes tener cualquier número de peones). No se conoce ninguna fórmula cercana para responder a este problema. Pero para un tablero de tamaño pequeño, esto fue calculado por computadoras.