Conexión de celdas por permutaciones de línea y columna en una cuadrícula finita

Me gustaría saber si el siguiente problema simple se ha estudiado antes y si se conoce alguna solución.

Sea G una cuadrícula finita (MxN), S un subconjunto de celdas de G (las "migajas"). Se dice que dos migajas están conectadas (localmente) si sus coordenadas difieren en un máximo (es decir, si se dibujan como cuadrados, comparten al menos un punto de esquina).

Ahora, uno puede intentar conectar las migajas (su conjunto como un todo) permutando las líneas y las columnas de la cuadrícula. En otras palabras, el objetivo es llegar a una permutación de las líneas y una permutación de las columnas para que dos migajas en la cuadrícula resultante estén conectadas por una cadena de migajas (localmente) conectadas.

Pregunta: ¿siempre hay una solución?

No sé cómo atacarlo. A falta de una idea mejor, he escrito un programa en bruto que busca soluciones por fuerza bruta (genera las permutaciones al azar y comprueba si la cuadrícula resultante tiene sus migajas conectadas). Hasta ahora, el programa siempre ha encontrado soluciones en cuadrículas pequeñas (10x10 o 7x14), y las cuadrículas más grandes están claramente fuera del alcance de su estrategia simplista (tomaría demasiado tiempo tropezar al azar con una solución).

Aquí hay un ejemplo de una cuadrícula resuelta por el programa:

Cuadrícula inicial (las migajas se denotan con X, las celdas vacías con puntos):

   0 1 2 3 4 5 6 7 8 9 
 0 X . X X . X . X X .
 1 X . . . . X . . . .
 2 . . X . . . . X . X
 3 . X . . X . X . . X
 4 . . . X . . . . . .
 5 X X . . . X X . X .
 6 . . . X . . . . X .
 7 X . X . . X . . . .
 8 X . . . X . . X X .

Solución:

   6 1 4 7 8 2 9 3 5 0
 1 . . . . . . . . X X
 4 . . . . . . . X . .
 5 X X . . X . . . X X
 8 . . X X X . . . . X
 7 . . . . . X . . X X
 0 . . . X X X . X X X
 3 X X X . . . X . . .
 6 . . . . X . . X . .
 2 . . . X . X X . . .

Naturalmente, el problema puede generalizarse fácilmente a cualquier dimensión d> 2. Supongo que podrían considerarse otras generalizaciones.

Gracias por adelantado,

Yann David

ds.algorithms graph-theory graph-algorithms Yann David
fuente

problema interesante ¿hay alguna aplicación?

Suresh Venkat

@ Tsuyoshi: tienes razón, la cifra que publiqué tiene una solución (la que proporcionaste). Lo borré.

Marzio De Biasi

Poste cruzado simultáneo se desaconseja. math.stackexchange.com/questions/83231/…

Tsuyoshi Ito

Probemos un argumento de conteo similar al de la versión anterior de mi respuesta, con más cuidado.

$n^2 2^{5q}$ $n^2$ $5q$ $n^2 2^{5q} (n!)^2$

$c$ $\binom{n}{c}^n$ $c$ $\exp(cn\log n-O(n))$ $q=cn$ $\exp(2n\log n+O(cn))$ $c>2$

David Eppstein
fuente

Estableciendo y descuidando los términos , perseguí su desigualdad para encontrar el punto de "equilibrio", obteniendo . El último valor es notablemente cercano a 26608.

c = 3

$c=3$

o (n)

$o(n)$

n > 6 * 2^{15} / e^{2}

$n > 6*2^{15}/e^2$

hardmath

Esa es una curiosa coincidencia numérica. Lo he preguntado en mathoverflow.net/questions/81368/…

David Eppstein el

De hecho, es una prueba elegante y convincente. (Me tomó un poco de tiempo detallar las aproximaciones para mi propio beneficio). Queda por ver si alguien logrará encontrar un contraejemplo concreto. El comentario anterior de @ hardmath sugiere que podría ser difícil (el CE sería una bestia fea); ahora no es necesario tener la misma cantidad de migas en todas las filas de un CE.

Yann David

Conexión de celdas por permutaciones de línea y columna en una cuadrícula finita

Respuestas: