Más corto posible forma inalcanzable

Question

Este es un seguimiento a cada forma posible, con una serpiente? .

Imagina un 2d de la serpiente formada por el dibujo de una línea horizontal de longitud $n$. En el entero de los puntos a lo largo de su cuerpo, esta serpiente puede girar su cuerpo por $90$ grados en sentido horario o en sentido antihorario. Si definimos a la parte delantera de la serpiente a estar en el extremo izquierdo para empezar, la rotación se mueve de la parte posterior de la serpiente y la parte frontal va a quedarse. Haciendo repetidas rotaciones se puede hacer un montón de diferentes serpiente formas del cuerpo.

Ahora vamos a definir un válido forma. Una forma es válida si puede ser formado a partir de una línea recta de la serpiente mediante la aplicación de más de un $90$ de grado de la curva en cada uno de los enteros puntos a lo largo de su cuerpo y no hay dos partes de la forma resultante se cruzan o se tocan.

Ahora podemos aplicar algunas reglas adicionales para decir una forma accesible. Una forma es alcanzable si es válido y es posible llegar a la orientación sin que alguna de las partes de el cuerpo de la serpiente de intersección o tocar en el medio. Esto incluye durante las rotaciones necesarias para doblar una parte en ángulos rectos.

Aquí están algunos ejemplos gracias a Martin Büttner.

Empezamos con la horizontal de la serpiente.

Ahora lo hacemos girar de la posición 4.

Terminamos después de la rotación en esta orientación.

Consideremos ahora esta orientación de una diferente de la serpiente.

Ahora podemos ver un movimiento ilegal, donde habría una superposición causados durante la rotación.

Cuando una rotación que pasa se va a mover la mitad de la serpiente con ella. Hacemos tiene que preocuparse acerca de si alguna de esta parte que es girado puede superponerse a una parte de la serpiente durante la rotación. Para simplificar, podemos asumir que la serpiente ha de ancho cero. Usted sólo puede girar en un punto particular de la serpiente hasta 90 grados en sentido horario de mostrador de las agujas del reloj. Para, nunca se puede pleno veces la serpiente en dos, ya que se trataba de dos rotaciones en el mismo punto en la misma dirección.

Formas que no se puede llegar

Una forma que no puede ser alcanzado es

(Gracias a Harald Hanche-Olsen para este ejemplo)

En este ejemplo, todos los adyacentes líneas horizontales son 1, aparte como son los verticales. Por tanto, no es un movimiento legal, a partir de esta posición y como el problema es reversible, por tanto, no hay manera de llegar desde la posición de partida.

Decimos que la longitud de una forma válida es simplemente la longitud de una serpiente que se pudieran formar. Por ejemplo, en el ejemplo de la forma por encima de la cual no puede ser alcanzado de longitud $59$.

¿Cuál es el plazo más breve posible inalcanzable válido forma?

Actual límite superior

David K dio una forma de la longitud de 31, que es inalcanzable. Es este el menor posible?

Answer 1

Teniendo en cuenta que la serpiente puede plegar o desplegar en cualquier uno de sus entero-coordenadas de los puntos en cualquier momento (siempre que no se toque a sí mismos durante o después de esta operación), la serpiente de longitud $31$ se muestra a continuación (basado en Harald Hanche-Olsen ejemplo) es inaccesible:

Si tomamos un punto $P$ en cualquier entero a lo largo de la serpiente de $D$ a $E$ inclusiva, $P$ es cercana a los us $B$ que $F$, es decir, $PB < PF$, así que cualquiera de los movimientos en $P$ haría que uno de los segmentos por encima o por debajo de $F$ a se cruzan el segmento que termina en $F$. (En particular, $DB = 2 < \sqrt5 = DF$, y todos los otros puntos son incluso más lejos de la mediatriz de $\overline {BF}$.) Si tomamos un punto $P$ en cualquier entero a lo largo de la serpiente de $C$ a $B$ inclusiva, entonces $QA \geq QE$, con igualdad sólo en $CA = \sqrt{13} = CE$; por lo tanto un movimiento en cualquiera de los puntos causaría $A$ a paso ya sea a través de la $E$, a través de algún segmento termina en $E$, o a través de alguna parte de la serpiente entre $E$ y $F$.

Es claramente imposible para la serpiente para plegar o desplegar en cualquier otro punto.

Ya que las mismas reglas de transformación que permiten la serpiente inicial de la forma de ser transformado en una forma accesible también permitiría a la forma accesible para ser transformado de vuelta a la serpiente de la forma inicial, de esta forma no se puede llegar.

Respuesta anterior

Cuando por primera vez me respondió esto me considera sólo "enderezar" se mueve cuando el pensamiento sobre la transformación de la serpiente vuelve a su forma inicial. Esto me llevó a proponer la siguiente forma de una serpiente de longitud $24$:

Como se observa en los comentarios, hay un movimiento legal en uno de los puntos a lo largo de el borde superior de esta forma (de hecho hay tres puntos en los que hay es un movimiento legal), después de que la serpiente no puede, obviamente, ser desplegado para su forma inicial. Por lo tanto este corto de snake forma sería inaccesible sólo bajo mucho más restringido conjunto de reglas en las que un ángulo recto de la curva en la que la serpiente, una vez hecho, no podía ser deshecha. Como restricción que no estaba prevista en el original de la declaración del problema, de esta forma no es una solución para el problema.

Answer 2

22 Unidades (Imperfecto)

Si todo subcomponentes se puede mover, no necesita ser un enganche estructura que impide la rotación en uno de los extremos en cualquier dirección. Creo que esta es la forma más corta posible para crear un gancho.

Editar:

Parece que mi respuesta falla aquí:

Voy a dejar esta respuesta aquí para la posteridad, pero de hecho es incorrecta.

Análisis del Problema

Suponiendo que partimos de una línea de longitud $L$ y, a continuación, realizar una secuencia de curvas de $b_i$ de $\pm 90$ grados en cualquier entero a lo largo de la línea de $\in [1, L]$. Es lo que llamamos la secuencia de un patrón de $P$. Podemos extender el conjunto de posibles curvas de $[-90, 90]$ a nos dan un sentido de continuidad. Curvas de exactamente $90$ grados será "todo curvas" y otras curvas será "parcial curvas". Los patrones que consta de solo conjunto de curvas se llama "conjunto de patrones".

Definición Un patrón también es inalcanzable si no es válido. Esta es sólo ligeramente diferente de la cuestión de la definición de inalcanzable, ya que también se aplica a los patrones sin considerar que curva se hizo antes.

Definición
$P_1 = P_2$ si hacen la misma forma de serpiente.

Lema
Dados dos enteros patrones de $P_i$ y $P_f$ tales que $P_f$ difiere de $P_i$ por toda una curva, hay parcial de los patrones que difieren de $P_i$ por un solo parcial de la curva y se diferencian de $P_f$ por un solo parcial de la curva. $P_f$ es inalcanzable desde $P_i$ si y sólo si existe al menos una parcial patrón que es inalcanzable o $P_f$ es inalcanzable.

Teorema de
Dados dos enteros patrones de $P_i$ y $P_f$. $P_f$ es accesible a partir de $P_i$ si y sólo si existe una secuencia de enteros de los patrones de $\{P_i = p_1, p_2, ..., p_{n-1}, p_n = P_f\}$ tal que para todos los pares adyacentes $(p_{i+1}, p_i)$, $p_{i+1}$ es accesible a partir de $p_i$.

Corolario
Deje que $P^L_o$ por el patrón de la línea recta de longitud $L$ sin curvas. Un patrón de $P$ es inalcanzable si es inalcanzable desde $P^L_o$.

Teorema de
Ser "inalcanzable" es una relación reflexiva sobre el conjunto de patrones. Ser "accesible" es una relación reflexiva sobre el conjunto de patrones.

Ahora, tenemos algunas herramientas para trabajar con el.

En realidad, hay dos clases de inalcanzable patrones en una inspección más cercana.

$$ \mathcal{P}_1 = \{P\ |\ P\text{ es inalcanzable desde }P_o^L\} \\ \mathcal{P}_2 = \{P\ |\ \forall P_ k\ = P, P\text{ es inalcanzable desde }P_k\} \\ \mathcal{P}_2 \subseteq \mathcal{P}_1 $$

Por ejemplo, dos elementos de $\mathcal{P}_1$ que no están en $\mathcal{P}_2$

Como se puede ver, estos dos patrones (longitud $39$ cada uno) son accesibles desde cada uno de los otros, pero no a partir de un plano de la serpiente. Simplemente de comprobar si un modelo puede ser doblada no descalificar de ser inalcanzable patrón. Podría ser que el menor inalcanzable patrón es un miembro de $\mathcal{P}_1$ y $\mathcal{P}_2$.