La simetría de la bicicleta de bloqueo de números

Question

Supongamos que usted tiene una combinación de candado de bicicleta de este tipo:

con $n$ diales y $k$ números en cada línea. Deje de $m(n,k)$ denotar el número mínimo de vueltas que siempre es suficiente para abrir la cerradura de cualquier posición de partida, donde a su vez se compone de rotación de cualquier número de anillos adyacentes por un lugar.

Por ejemplo $m(2,10)=6$ y $m(3,10)=10$.

He encontrado un algoritmo eficiente para calcular estos números, lo que revela una simetría que no puedo actualmente explicar:

$m(n, k+1) = m(k, n+1)$

Este es un sorprendente simetría que creo que tiene una explicación sencilla. Puede alguien encontrar uno?

Aquí está la tabla de valores para las pequeñas $n$ y $k$, exhibiendo la conjetura de simetría:

n\k| 2 3 4 5 6 7 8 9 10
---+---------------------------------------------
1 | 1 1 2 2 3 3 4 4 5
2 | 1 2 2 3 4 4 5 6 6
3 | 2 2 4 4 6 6 8 8 10
4 | 2 3 4 6 6 8 9 10 12
5 | 3 4 6 6 9 9 12 12 15
6 | 3 4 6 8 9 12 12 15 16
7 | 4 5 8 9 12 12 16 16 20
8 | 4 6 8 10 12 15 16 20 20
9 | 5 6 10 12 15 16 20 20 25
10 | 5 7 10 12 15 18 20 24 25

Answer 1

Se ha tomado un par de días, pero creo que en la última puede responder a mi propia pregunta. La estrategia es mostrar que, para cada combinación de los $(n,k)$ de bloqueo, hay una combinación de la $k-1,n+1)$ de bloqueo que necesita el mismo número de vueltas para desbloquear. El argumento comienza por la agrupación de bloqueo de combinaciones en clases de equivalencia de tal manera que las combinaciones equivalentes requieren el mismo número de vueltas para abrir.

---

Asumir que todo el destino de combinación, que abre la cerradura, es de $n$ ceros.

El primer truco es que yo antes: en lugar de buscar en las posiciones de la marca, a mirar las diferencias entre las posiciones adyacentes de la marca. En su propio, esto no desechar cualquier información – el proceso es reversible – pero abre la puerta a una simplificación: el orden de las diferencias no importa. Así que vamos a decir que dos combinaciones son equivalentes si tienen el mismo conjunto múltiple de las diferencias, y vamos a escribir las diferencias como una secuencia no decreciente, para dar una forma canónica.

Para motivar a la siguiente identificación vamos a hacer, vamos a considerar un ejemplo de combinación de la $(n=4, k=10)$-lock: 2593, que diferencias tiene 23447. Las diferencias suma de $2k$, lo que significa que – como se ha explicado en mi post del blog original – que podemos ignorar a los dos grandes diferencias y agregar los demás, por lo que esta combinación se lleva $2+3+4 = 9$ gira para abrir. Pero, puesto que los dos mayores diferencias ni siquiera entrar en el cálculo, que podría haber sido cualquier par de números que se encuentran a menos de $4 dólares y la suma de $11$. En particular, podrían haber sido de $5$ y $6$ por lo que las diferencias eran 23456. En este sentido, las combinaciones de 2593 y 2594 son equivalentes. Vamos a denotar esta clase de equivalencia por parte de la secuencia (2,3,4), que vamos a llamar a una secuencia de bloqueo para el $(n, k)$-lock. Observe que el número de vueltas necesario para abrir la cerradura es la suma de los términos de la secuencia de bloqueo.

Ahora vamos a caracterizar el bloqueo de secuencias. Deje de $d_1, d_2, \dots, d_m$ ser una secuencia no decreciente de números naturales menores que $k$ que tienen una longitud de m $\leq$ n; esta es una secuencia de bloqueo para el $(n,k)$-lock si estas dos desigualdades se sostiene:

$\sum_{i=1}^{m}d_i+(n+1-m)(k-1)\geq (n+1-m)k$

$\sum_{i=1}^{m}d_i + (n+1-m)d_m\leq(n+1-m)k$

Que puede ser simplificado a

$n+1-m\leq\sum_{i=1}^{m}d_i\leq(n+1-m)(k-d_m)$

La primera desigualdad es un poco molesto, así que vamos a deshacerse de él haciendo una última identificación: vamos a identificar bloqueo de secuencias que difieren sólo por ceros a la izquierda, y asumir una forma canónica que no tiene ceros a la izquierda. Si la primera desigualdad falla, podemos forzar a que lleve a cabo mediante la adición de ceros a la izquierda, aumentando $m$. Así que ahora estamos a la izquierda con

$\sum_{i=1}^{m}d_i\leq(n+1-m)(k-d_m)$

Me gusta imaginar esta condición en el sentido de, "¿hay habitaciones en el ático para todas las cajas?". Tal vez tendrá más sentido si se me dibuja una imagen:

Esta foto representa la secuencia de bloqueo de $(1,1,2,2,2,2,3,3)$ como un arreglo de 16 casillas, y un "ático" de área $(n+1-m)(k-d_m)$, todo dentro de un $(n+1)\times k$ rectángulo.

Ahora vamos a darle la vuelta, como la conjugación de un Joven diagrama, y mover el ático nuevo a la parte superior:

Todavía tenemos la misma disposición de las cajas – en particular el valor de $\sum_{i=1}^{m}d_i$ sigue siendo la misma – y el ático es el mismo tamaño. Entonces el conjugado de la secuencia – $(2,6,8)$ en este ejemplo – es una secuencia válida para el $(k-1, n+1)$de bloqueo única condición de que la original era una secuencia válida para el $(n, k)$-lock.

Así, hemos demostrado que cada secuencia de bloqueo para el $(n,k)$de bloqueo puede ser transformada en una secuencia de bloqueo para el $(k-1,n+1)$de bloqueo que tiene la misma suma. De ello se desprende que toma al menos como muchos movimientos, en general, para abrir un $(k-1,n+1)$de bloqueo como un $(n,k)$-lock. Desde que esto funciona en ambas direcciones, se puede concluir que la $m(n,k) = m(k-1, n+1)$.

---

Otra forma de mirarlo es señalar que lo anterior implica

$m(n,k) = \max\{\min\{ac,bd\}\ |\ a+b=n+1,c+d=k\mbox{ para }a,b,c,d\in\mathbb{N}\}$

que es simétrica en $n+1$ y $k$. Esta expresión también sugiere otra manera de calcular $m(n,k)$.

Answer 2

Primero vamos a considerar una forma mucho más simple de la situación. Si, en lugar de mover cualquier grupo de adyacentes de la marca, sólo puede mover una esfera, el número máximo de vueltas es trivial-es igual a $kn/2$. Tenga en cuenta que esta expresión muestra una especie de simetría muy similar a lo que estás viendo. Para ser jargony, el espacio de estado -- número de combinaciones -- tiene un volumen de $kn$, que es una propiedad conmutativa de la expresión, y sólo podemos movernos a través de uno de los cuadrados de espacio de estado en un momento.

Ahora, si nos fijamos en el problema real, el espacio de estado es todavía de volumen $kn$, pero podemos movernos a través de $k$ casillas a la vez, con algunas restricciones. Es más fácil analizar si sólo se puede mover a través de uno de los cuadrados, por lo que podemos ver en el espacio de las diferencias: 3879 se convierte 592 y 23856 se convierte en 1571. En el espacio de diferencias que sólo pueden pasar dos diferencias a la vez, uno arriba, uno abajo, por lo que 1571 podría convertirse en 0572-pero más importante aún, tenemos un volumen de $(k-1) \times n$ y nos movemos de una cantidad constante, por lo que esperamos ver una longitud de ruta de acceso de $\Omega((k-1)n)$.

Ahora, la expresión $m(n, k) = \Omega((k-1)n)$ exhibe la observada simetría! Es sólo la conmutación -- si tomamos $m(k-1, n+1)$ nosotros, obviamente, tienen el mismo "volumen" de la "diferencia " espacio". Hay algunos intuición aquí, pero aún no hemos derivado el camino más corto.

Voy a tomar prestado su expresión $t = \sup_x(xk - xq - \min(r,x)$ para $xk = q(n+1) + r$ y tenga en cuenta que el límite superior y el límite inferior se realiza precisamente donde $n+1 | xk$ y $n+1 | x(k-1)$, y que son proporcionales a $x(n+1-x)$, así que han compartido un máximo de $x = (n+1)/2$. Esto nos da la ecuación de diophantine $q(n+1) = xk$ y si sustituimos $x \aprox (n+1)/2$ tenemos $q \aprox k/2$.

Si ambos son enteros -- si $n$ es impar y $k$ es aún -- tenemos $t(n, k) = m(n, k) = k(n+1)/4$. Así que un poco más sencillo ya, y sigue la pauta de que es agradable.

Sin embargo, la ecuación no tiene una solución satisfactoria si $k$ es impar o $n$ es par, por lo que representa una suficiente pero no necesaria condición para un máximo. Podríamos tratar de aproximadamente resolver la ecuación mediante la elección de $x = (n+1)/2$, $q = k/2$, y la búsqueda de una cerca de celosía punto. Para $n = 200$, $k = 9$ podemos elegir $x = (n+1)/2 - (n+1)/2k = 101.5 - 11.1 = 89.9$, que es cerca de la verdadera máximo de $x = 89$ y sugerente de un patrón más general. Me he pasado una hora en esta ya y aunque debería volver a trabajar.

EDIT: supongo que la conclusión es que la ecuación de Diophantine $q(n+1) = xk$ es la misma si tomamos $n \rightarrow k-1$, $k \rightarrow n+1$ obtener $qk = x(n+1)$. Aproximado de las soluciones a esta ecuación corresponden a las soluciones del problema general.