I've been trying to figure out a general formula to calculate the maximum relative misalignment of m identical rings with n symbols each on a combination lock like the one shown below.
By "maximum relative misalignment" I mean the maximum number of turns that would be required to align all the rings with each other so their numbers match up.
You could think of this as the maximum number of turns that would be needed to unlock the combination shown, if the combination lock will unlock if all the numbers between the dots are the same number.
For this particular lock where m=5 and n=10, I've calculated the number to be 12.
You could also think of this as the maximum total number of rotational shifts required to align m arrays containing the same n unique numbers each.
I've been unable to figure out a generalized formula for this even though it seems like it shouldn't be terribly complicated.
I brute forced the answer for m and n between 2 and 12 and the results were as follows:
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
I noticed that the value seems to be the same if you swap m and n.
I've determined the formula for even values of m and n seems to just be (n/2)*(m/2)
Thanks for any help
Partial result: Proof that $f(m,n) = mn/4$ when $m,n$ are even.
Let $f(m,n)$ be the number you seek, i.e.
$$f(m,n) = \max_x \min_a g(x,a)$$
$$\text{where: } g(x,a) \equiv \sum_{j=1}^m dist(x_i,a)$$
where $[n] = \{0, 1, ..., n-1\}, x \in [n]^m, a \in [n]$ and $dist()$ is the shortest distance from $x_i$ to $a$ along the $n$-node ring, and $g(x,a)$ is the total distance of moving everybody to position $a$.
Theorem: For $m, n$ even, $f(m,n) = mn/4$.
Proof: Consider a given $x$ and suppose $a$ is an optimum, i.e., it minimizes the sum of distances. Let $b = a + n/2 \pmod n$, i.e. the exactly opposite position.
Lemma: $g(x,a) + g(x,b) = mn/2$
Proof: For every $x_i, dist(x_i,a) + dist(x_i,b) = n/2$ because it simply traverses one arc or the other arc of the half-circle from $a$ to $x_i$ to $b$. Sum over all $m$ and we get the result.
Continued proof of theorem: Since $a$ is optimal by assumption, $g(x,a)\le g(x,b)$, which combined with the lemma, means $g(x,a) \le mn/4$.
OTOH, $g(x,a) = mn/4$ is achievable, so the bound is tight. E.g. just put $m/2$ at one position and the other $m/2$ at the exact opposite position.