Clavos y cuerdas y pinturas

Question

Esta pregunta se basa en la "Imagen" a prueba a los desafíos de Rankk.org...

IDEA: Usted quiere tener una pintura utilizando clavos en una pared y la cadena. La cadena está unido a los lados izquierdo y derecho de la pintura y las uñas son entre (digamos que en una línea recta horizontal por simplicidad).

PREGUNTA: El objeto es encontrar maneras de hacer esto para satisfacer diversas necesidades. Por ejemplo, en caso de que un clavo se saca, va a caer. O, de manera que si cualquiera de los dos uñas (pero no uno) son sacados va a caer. En particular, quiero buscar soluciones a corto o incluso un método para construir todas las posibles soluciones. Básicamente, ¿qué es exactamente la estructura matemática y cuáles son los principales resultados o lo que sea.

Efectos VISUALES: Aquí yo use mayúsculas para los inversos.

TEORÍA: Primera nomenclatura. Supongamos que tenemos tres clavos: $a$, $b$ y $c$. Si pasamos por encima de la primera uña rightwards, es lo que llamamos la $a$, pero si tenemos que ir a través de ella hacia la izquierda, lo que llamamos la $a^{-1}$. Luego, si nos conatenate o multiplicar, es decir, hacer una después de la otra. Así, por ejemplo, $abc$ corresponde a la cadena de ir a través de más de la parte superior de los tres clavos de izquierda a derecha. En ese caso, los tres clavos tendría que ser removido antes de que la pintura se cayó. Algo como $aba^{-1}$ significa que es un bucle alrededor de $b$, pero una especie de colgante en $a$. Sólo $b$ debe ser eliminado para que se caiga.

Obviamente $aa^{-1}$ cancela. Y $a^5$ significa un montón de bucles. La eliminación de un clavo simplemente significa la eliminación de todos sus apariciones en la fórmula. La pintura va a caer si todo se reduce a la identidad. Por ejemplo,) $bca^{-1}cac$ hace $bc^3$ si $a$ clavo se saca. Tal vez la herramienta más poderosa que he encontrado es que se puede utilizar un tipo de conjugación como un operador "or". Se enreda por las dos partes. Por ejemplo, $aba^{-1}b^{-1}$ va a caer si $a$ o $b$ son eliminados. El complemento "y" operador es simplemente la multiplicación. Por lo $abcb^{-1}a^{-1}c^{-1}$ $ab$ conjugado con $c$ y caerán si $c$ es eliminado o ambas $a$$b$.

Como punto de partida, que pueden encontrar a una cadena corta de cuatro clavos que cae si alguna de las dos se sacan?

PS. Puedo dar más ejemplos...

Answer 1

Una posible solución (en la primera situación, es decir que se requieren exactamente un clavo retiró en orden para que la foto se caen) para clavos $\alpha_1, \dots, \alpha_n$ sería afirmar conmutador: $\gamma = [\alpha_1,\dots, \alpha_n]$ donde$[a_1,a_2] = a_1a_2a_1^{-1}a_2^{-1}$$[a_1, \dots, a_n,a_{n+1}] = [[a_1,\dots, a_n],a_{n+1}]$.

El problema es completamente descrito de la siguiente manera: Encontrar un elemento $\gamma$ de la libre grupo de $F$ en los generadores $\alpha_1, \dots, \alpha_n$, de tal manera que $\gamma$ no es trivial y se encuentra en el núcleo de todos los mapas de proyección $F \to F/\langle \alpha_k \rangle$.

Ahora el reto al final de tu post: Deje $\{a_1,a_2,a_3\} := a_1a_2a_3a_1^{-1}a_2^{-1}a_3^{-1}$. Un elemento $\gamma$ de la libre grupo de $F$ generado por $\alpha_1,\alpha_2,\alpha_3,\alpha_4$, lo cual no es trivial, cuyas proyecciones $F \to F/\langle \alpha_k\rangle$ no son triviales, pero que se encuentra en el núcleo de las proyecciones $F \to F/\langle \alpha_k, \alpha_j \rangle$ siempre $k \neq j$ está dado por $\gamma = [\{\alpha_1,\alpha_2,\alpha_3\},\{\alpha_1,\alpha_2,\alpha_4\},\{\alpha_1,\alpha_3,\alpha_4\},\{\alpha_2,\alpha_3,\alpha_4\}]$. Ahora debería ser bastante fácil ver cómo generalizar estos resultados (utilizando más las uñas, o que requieren más clavos para ser arrancado) utilizando sólo $[]$$\{\}$.

Answer 2

Relevante: Colgar cuadros Puzzles por Demaine et al:

Nos muestran cómo colgar una foto por envolver la cuerda alrededor de $n$ uñas, haciendo un polinomio número de giros, de tal manera que la imagen cae cuando cualquiera de los $k$ $n$ uñas se vuelven a quitar, y la imagen queda colgado cuando menos de $k$ uñas se vuelven a quitar. Esta construcción hace que para un poco de diversión matemática magia actuaciones. De manera más general, podemos caracterizar las posibles funciones Booleanas cuando la caracterización de la imagen cae en términos de que las uñas se vuelven a quitar como todos monotono funciones Booleanas. Esta construcción requiere de un número exponencial de giros en el peor de los casos, sino exponencial de la complejidad es casi siempre necesario para funciones generales.

"Todos los monotono funciones Booleanas" significa lo siguiente: Supongamos que tenemos un conjunto de $S$ de los clavos, y se selecciona una familia de $\mathcal F$ de los subconjuntos de a $S$. Quitar algún subconjunto $S'$ de los clavos de la pared, y desea que la imagen a caer si y sólo si $S'\in\mathcal F$.

Es posible colgar la imagen de modo que quede sólo si un conjunto de clavos $S'$ es eliminado en $\mathcal F$ si y sólo si $\mathcal F$ tiene las siguientes propiedades:

• Si $S'$ es un elemento de $\mathcal F$, por lo que es cualquier superconjunto de a $S'$.

• Si $S'$ es no un elemento de $\mathcal F$, ni es cualquier subconjunto de a $S'$.

Así, por ejemplo, si desea que la imagen a caer si las uñas $A$ $B$ se retiran, usted tiene que aceptar que también va a caer si $A$, $B$, y algunos otros clavos se quitan, y si desea que la imagen permanezca si sólo $A$ $B$ se retiran, usted tiene que aceptar que también permanecerá hasta si sólo $A$ o sólo $B$ es eliminado.