¿Cómo encontrar la máxima desalineación relativa de las anillas numeradas en una cerradura de combinación?

Question

He estado intentando averiguar una fórmula general para calcular la máxima desalineación relativa de m anillos idénticos con n símbolos cada uno en una cerradura de combinación como la que se muestra a continuación.

Por "desalineación relativa máxima" me refiero al número máximo de vueltas que serían necesarias para alinear todos los aros entre sí de manera que sus números coincidan.

Se podría pensar en esto como el número máximo de vueltas que se necesitarían para desbloquear la combinación mostrada, si la cerradura de combinación se desbloquea si todos los números entre los puntos son el mismo número.

Para esta cerradura en particular, donde m=5 y n=10, he calculado que el número es 12.

También se puede pensar en esto como el número total máximo de desplazamientos de rotación necesarios para alinear m matrices que contienen los mismos n números únicos cada una.

No he podido encontrar una fórmula generalizada para esto aunque parece que no debería ser terriblemente complicado.

He forzado la respuesta para m y n entre 2 y 12 y los resultados han sido los siguientes:

    2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17  18  19
2   1   1   2   2   3   3   4   4   5   5   6   6   7   7   8   8   9   9
3   1   2   2   3   4   4   5   6   6   7   8   8   9   10  10  11  12  12
4   2   2   4   4   6   6   8   8   10  10  12  12  14  14  16  16  18  18
5   2   3   4   6   7   8   9   10  12  13  14  15  16  18  19  20  21  22
6   3   4   6   7   9   10  12  13  15  16  18  19  21  22  24  25  27  28
7   3   4   6   8   10  12  13  15  17  18  20  22  24  25  27  29  30  32
8   4   5   8   9   12  13  16  17  20  21  24  25  28  29  32  33  36  37
9   4   6   8   10  13  15  17  20  22  24  26  28  31  33  35  37  40  42
10  5   6   10  12  15  17  20  22  25  27  30  32  35  37  40  42  45  47
11  5   7   10  13  16  18  21  24  27  30  32  35  38  40  43  46  49  51
12  6   8   12  14  18  20  24  26  30  32  36  38  42  44  48  50  54  56
13  6   8   12  15  19  22  25  28  32  35  38                          
14  7   9   14  16  21  24  28  31  35  38  42                          
15  7   10  14  18  22  25  29  33  37  40  44                          
16  8   10  16  19  24  27  32  35  40  43  48                          
17  8   11  16  20  25  29  33  37  42  46  50                          
18  9   12  18  21  27  30  36  40  45  49  54                          
19  9   12  18  22  28  32  37  42  47  51  56                          

Me he dado cuenta de que el valor parece ser el mismo si se intercambian m y n.

He determinado que la fórmula para valores pares de m y n parece ser simplemente (n/2)*(m/2)

Gracias por cualquier ayuda

Answer 1

Resultado parcial: Prueba de que $f(m,n) = mn/4$ cuando $m,n$ están igualados.

Dejemos que $f(m,n)$ sea el número que se busca, es decir

$$f(m,n) = \max_x \min_a g(x,a)$$

$$\text{where: } g(x,a) \equiv \sum_{j=1}^m dist(x_i,a)$$

donde $[n] = \{0, 1, ..., n-1\}, x \in [n]^m, a \in [n]$ y $dist()$ es la distancia más corta desde $x_i$ a $a$ a lo largo del $n$ -anillo de nodos, y $g(x,a)$ es la distancia total de desplazamiento de todos a la posición $a$ .

Teorema: Para $m, n$ incluso, $f(m,n) = mn/4$ .

Prueba: Consideremos un determinado $x$ y supongamos $a$ es un óptimo, es decir, minimiza la suma de distancias. Sea $b = a + n/2 \pmod n$ es decir, la posición exactamente opuesta.

Lema: $g(x,a) + g(x,b) = mn/2$

Prueba: Para cada $x_i, dist(x_i,a) + dist(x_i,b) = n/2$ porque simplemente atraviesa un arco o el otro arco del semicírculo de $a$ a $x_i$ a $b$ . Suma de todos los $m$ y obtenemos el resultado.

Continuación de la demostración del teorema: Dado que $a$ es óptima por supuesto, $g(x,a)\le g(x,b)$ lo que, combinado con el lema, significa que $g(x,a) \le mn/4$ .

POR OTRO LADO, $g(x,a) = mn/4$ es alcanzable, por lo que el límite es ajustado. Por ejemplo, basta con poner $m/2$ en una posición y en la otra $m/2$ en la posición exactamente opuesta.