6
$\begingroup$

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.

1

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

$\endgroup$
  • 1
    $\begingroup$ Possible duplicate of Optimally scramble the combination lock $\endgroup$ – Mike Earnest Apr 10 at 20:16
  • 2
    $\begingroup$ If you want to change a question, don't delete it and ask a new question, but just edit the question, using the edit link at the bottom. $\endgroup$ – Rob Arthan Apr 10 at 20:49
  • $\begingroup$ What is counted as a turn? Moving one ring one space in either direction? $\endgroup$ – Servaes Apr 10 at 20:52
  • $\begingroup$ @Servaes Yes. Moving the ring one space in either direction. If it were defined as moving on ring any number of spaces in any direction the answer would be trivial. $\endgroup$ – Conor Henry Apr 10 at 20:54
  • $\begingroup$ When you say the lock "will unlock if the numbers between the dots are the same number", am I right in thinking that it can be any number, rather than some fixed number: i.e., it will unlock when you get to all 0s or all 1s or all 2s or ...? $\endgroup$ – Rob Arthan Apr 10 at 20:58
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This makes a lot of sense. Thanks! I'm looking into deriving the values for m and n being both odd. I've noticed when m and n are both odd and m=n, the value is given by ((n-1)/2 + 1)((n-1)/2). $\endgroup$ – Conor Henry Apr 17 at 19:14
  • 1
    $\begingroup$ @ConorHenry - this is a fascinating problem. I think many things are "obvious" but hard to prove. e.g. for the $m=n$ case, i think it is "obvious" the max $x$ is when one $0$ occupies each position, i.e. the perfectly spread scenario. that scenario indeed gives $k(k+1)$ where $n=m=2k+1$. But how to prove that's the max? I have no idea yet. I have some other partial results which I hope to post when I have more time. $\endgroup$ – antkam Apr 18 at 5:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.