Considere la posibilidad de un arreglo de n monedas de diez centavos en una línea recta. Un movimiento consiste en tomar una moneda de diez centavos y girando sobre (de cabeza a cola, o viceversa) y de hacer lo mismo a cada uno de sus vecinos. Si la moneda está en el extremo de la línea, entonces va a tener sólo un vecino. Por ejemplo, si el arreglo es HHTH y elige la segunda moneda de diez centavos, entonces su medida podría resultar en TTHH. La pregunta general es la siguiente: Dado cualquier arreglo de n monedas de diez centavos, es posible encontrar una secuencia de acciones para llevar a todos los jefes?
Respuestas
¿Demasiados anuncios?
Gracias @saulspatz de la evidencia numérica, sin la cual no podría haber encontrado esta la prueba:
Para cualquier longitud de $k$, pasando de la izquierda a la derecha en un solo paso, encontrar el primer T, darle la vuelta a H sin afectar a todas las Hs a su izquierda. E. g. HHTTH -> HH(TTH) -> HH(HHT). Al hacerlo, se quedan con todo Hs (de hecho) o todo Hs excepto la posición derecha es T. En este último caso:
si $k = 3n$, usted tiene $3n-1$ Hs. Ir de derecha a izquierda en una sola pasada, de la vuelta no la superposición de conjuntos de 3 monedas a T, y el conjunto final de las 2 monedas también a T. Ahora usted tiene todas las Ts. Voltear todo a Sa, que es factible debido a que $k=3n$.
si $k = 3n+1$, usted tiene $3n$ Hs. Hacer lo mismo que antes para llegar a todos los Ts. Ahora voltear como $2 + 3 + 3 + \cdots + 3 + 2$ de nuevo a todos Hs.
El procedimiento anterior de manera constructiva demuestra que el problema es solucionable para todos los $k= 3n$ o $3n+1$.
Para mostrar que $k=3n+2$ NO es solucionable primera observar que en cualquier secuencia de movimientos, si se hace el mismo movimiento, es decir, en una determinada posición $i$, dos veces, que sus efectos se anulan, INCLUSO SI se hace por separado (discreta) de tiempo en la secuencia. Por lo tanto, cualquier movimiento de la secuencia (de cualquier longitud), en realidad, se reduce a un subconjunto de todos los posibles movimientos. Hay $k$ movimientos posibles, por lo que hay sólo $2^k$ subconjuntos. Para que el problema se pueda resolver, cada subgrupo debe tener un efecto DIFERENTE, ya que hay $2^k$ posibles posiciones de partida. Sin embargo, para $k=3n+2$, los movimientos $3 + \cdots + 3 + 2$, y los movimientos $2 + 3 + \cdots + 3$ tiene el mismo efecto. Entonces, no. de todos los posibles efectos de $< 2^k$ y algunos la posición de partida debe ser irresolubles.
Punto de VISTA ALTERNATIVO: El movimiento en la posición $j$ ($1 \le j \le k$) puede ser modelado como un $k$-vector $v_j$ $1$s en las posiciones $j-1, j, j+1$ (ignorar fuera de rango de las entradas) y $0$ en todas las demás. A continuación, haciendo la $j$th mover y, a continuación, el $j_2$th movimiento puede ser modelado como $v_j + v_{j_2}$ mod2, y haciendo un subconjunto $M$ de los movimientos pueden ser modelados como $\sum_{j \in M} v_j$. Esto sugiere una representación de la matriz. (Suponga mod2 a partir de ahora.)
Deje $A$ el (tri-diagonal) $k \times k$ matriz de donde $A_{ij} = 1$ si $|i-j|\le 1$ $0$ lo contrario. Así que un subconjunto $M$ de los movimientos pueden ser representados como una $k$-vector $m$ donde $m_j = 1$ si $j \in M$ $0$ lo contrario, y haciendo esos movimientos tienen efecto $A m$, es decir, el resultado final es el volteo de todas las posiciones $p$ donde $[Am]_p = 1$.
Cualquier posición de partida puede ser representado por una $k$-vector $t$ donde $t_j = 1$ si $j$th posición es T y $0$ si es H. Así que la solución de $t$ significa encontrar $m$ s.t. $t = Am$. Por lo tanto, el problema tiene solución para todos los $t$ fib $A$ tiene rango completo, o, equivalentemente, $det(A) \neq 0$. Deje $d_k$ ser el determinante de la $k\times k$ versión de la $A$ matriz. A partir de la estructura de la tridiagonal de las matrices mirando a los menores de edad, uno puede mostrar $d_k = d_{k-1} + d_{k-2}$. Mirando de $d_2 = 0, d_3 = 1$ el resto de las secuencias de va $1, 0, 1, 1, 0, 1, 1, 0, 1$ etc. Esto demuestra una vez más, el problema es solucionable (para todas las posiciones de partida) iff $k = 3n$ o $3n+1$.
Además, para $k=3n+2$, mientras que $A_{k \times k}$ no tiene rango completo, contiene $A_{(k-1)\times (k-1)}$ como un bloque y el bloque tiene rango completo, por lo $rank(A_{k \times k}) = k-1$. Por lo tanto, el número de solucionable posiciones de partida $=|range(A_{k \times k})| = 2^{k-1}$, es decir, exactamente la mitad de las posiciones de partida son resolubles.
Por CIERTO, aquí se $A^{-1}$$k=12$$13$, sólo por diversión. El $j$ésima columna (o fila), es la manera de resolver un T $j$. Los patrones son bastante diferentes para $3n$$3n+1$.
0 1 1 0 1 1 0 1 1 0 1 1
1 1 1 0 1 1 0 1 1 0 1 1
1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 1 1 0 1 1
1 1 0 1 1 1 0 1 1 0 1 1
1 1 0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 1 1
1 1 0 1 1 0 1 1 1 0 1 1
1 1 0 1 1 0 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1
1 1 0 1 1 0 1 1 0 1 1 1
1 1 0 1 1 0 1 1 0 1 1 0
1 0 1 1 0 1 1 0 1 1 0 1 1
0 0 1 1 0 1 1 0 1 1 0 1 1
1 1 0 0 0 0 0 0 0 0 0 0 0
1 1 0 1 0 1 1 0 1 1 0 1 1
0 0 0 0 0 1 1 0 1 1 0 1 1
1 1 0 1 1 0 0 0 0 0 0 0 0
1 1 0 1 1 0 1 0 1 1 0 1 1
0 0 0 0 0 0 0 0 1 1 0 1 1
1 1 0 1 1 0 1 1 0 0 0 0 0
1 1 0 1 1 0 1 1 0 1 0 1 1
0 0 0 0 0 0 0 0 0 0 0 1 1
1 1 0 1 1 0 1 1 0 1 1 0 0
1 1 0 1 1 0 1 1 0 1 1 0 1
saulspatz
Puntos
116
No una respuesta, pero demasiado largo para un comentario. Escribí esta secuencia de comandos de python
import numpy as np
from scipy.sparse.csgraph import connected_components
for k in range(4,11):
n=2**k
masks = {3}
j=0
while 7*2**j < n:
masks.add(7*2**j)
j+= 1
masks.add(n//2+n//4)
A = np.zeros((n,n), dtype = int)
for i in range(n):
for m in masks:
A[i, i^m] = 1
supernodes=connected_components(A)
print(k, supernodes[0])
Para $4\le k< 11,$ se calcula la matriz de adyacencia del grafo cuyos vértices son los $k-$poco cadenas binarias, donde dos vértices son adyacentes si uno se puede transformar en la otra por un solo tirón (sustituyendo $1$'s y $0'$s de cabezas y colas, por supuesto).
A continuación, calcula los componentes conectados de la gráfica. El problema es posible si y sólo si el número es uno. Aquí está el resultado:
4 1
5 2
6 1
7 1
8 2
9 1
10 1
El guión es muy rápido, por lo que probablemente puede ser usado para determinar cuál es el patrón. supernodes[1] es una lista que codifica los componentes. Por ejemplo, cuando se $k=5$ esta lista
[0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0]
Esto significa que TTTTT es en el componente $0$, TTTTH y TTTHT están en el componente $1,$ y así sucesivamente. Tal vez uno podría ser capaz de encontrar un patrón y demostrar que es imposible en ciertos casos, pero estoy dudosa.
La secuencia de comandos se atasca considerablemente $k$ aumenta. Me encontré con que $k=11$ es el único otro valor por debajo de $14$ para lo cual es imposible. Me aburrí de espera para la $k=14$ caso para terminar.
EDITAR
He comprobado que es imposible para $n=14$ así que ahora estoy dispuesto a adivinar que es posible, excepto cuando el $n\equiv2\pmod3$. Una cosa que he comprobado que puede ser útil, es que en el imposible de los casos, hay exactamente dos componentes conectados, y que si dos cadenas diferentes sólo en el último carácter, (o sólo en la primera letra, por simetría), entonces es imposible transformar una en la otra.
Así, por ejemplo, cuando se $n=5,$ $4-$cadena de caracteres se produce como un prefijo de una palabra en cada componente hasta ahora, no he averiguado cómo se decide que los componentes de las cinco cadenas de caracteres de ir. Aquí es un componente $0$:
['TTTTT', 'TTTHH', 'TTHTT', 'TTHHH', 'THTTH', 'THTHT', 'THHTH', 'THHHT', 'HTTTH', 'HTTHT', 'HTHTH', 'HTHHT', 'HHTTT', 'HHTHH', 'HHHTT', 'HHHHH']
y aquí es componente $1$:
['TTTTH', 'TTTHT', 'TTHTH', 'TTHHT', 'THTTT', 'THTHH', 'THHTT', 'THHHH', 'HTTTT', 'HTTHH', 'HTHTT', 'HTHHH', 'HHTTH', 'HHTHT', 'HHHTH', 'HHHHT']
Dada una cadena de cinco caracteres $\{H,T\}$ cómo podemos decidir qué componente se debe ir sin buscar los componentes?
