Skip to main content
4 of 4
added 264 characters in body

EDIT: I've just realized that I answered a different question than was asked. The answer assumes that each of the $k$ dials needs to turn by 1 in the same direction. I'm leaving the answer as is in case someone will find the modified problem interesting.

TL;DR: the graph is connected iff $k$ and $n$ are co-prime.

I think the question can be rephrased as follows. Consider the set of all vectors $\mathbb Z_n^d$ in which exactly $k$ coordinates are 1, and the rest are 0. What is the integer span $S_n$ of this set?

Let's first consider this question in $\mathbb Z^d$ instead, and ask for the corresponding span $S$.

For distinct $i_1, ..., i_k$, let $A(i_1, ..., i_k)$ be $(x_1, ..., x_d) \in \mathbb Z^d$ such that $x_j = 1$ if $j \in \{i_1, ..., i_k\}$, and 0 otherwise. By definition, $A(i_1, ..., i_k) \in S$.

Let $B(i, j)$ be $(x_1, ..., x_d) \in \mathbb Z^d$ such that $x_i = 1$, $x_j = -1$, and all other coordinates are 0. Note that $B(1, 2) = A(1, 3, 4, ..., k+1) - A(2, 3, ..., k+1) \in S$. Since problem is invariant to co-ordinate permutations, $B(i, j) \in S$ for any $i, j$.

The coordinates $(x_1, ..., x_d)$ of any $A(i_1, ..., i_k)$ sum to $k$. Therefore any $(x_1, ..., x_d) \in S$ satisfies $\sum x_i = 0 \pmod k$. We'll now show the reverse: any $(x_1, ..., x_d) \in \mathbb Z^d$ with $\sum x_i = 0 \pmod k$ belongs to $S$. We'll show this by starting from $(x_1, ..., x_d)$ and subtracting vectors in $S$ until we reach $(0, ..., 0)$.

By assumption, $\sum x_i = mk$ for some $m$. By subtracting $m A(1, 2, ..., k)$, we obtain a new $(x_1, ..., x_d)$ such that $\sum x_i = 0$. If $(x_1, ..., x_d) \neq (0, ..., 0)$, then we take some $x_i < 0$ and some $x_j > 0$, and add $B(i, j)$ to $(x_1, ..., x_d)$. This will preserve $\sum x_i = 0$, and reduce $\sum |x_i|$. So, after repeating the last step finitely many times, you'll obtain $(0, ..., 0)$. This proves that the initial $(x_1, ..., x_d)$ was in $S$.

This solves the problem for $\mathbb Z^d$ by showing that $S = \{(x_1, ..., x_d) | \sum x_i = 0 \pmod k\}$. To find the span $S_n \subseteq \mathbb Z_n^d$, notice that $(y_1, ..., y_d) \in S_n$ iff $(y_1, ..., y_d) + n(m_1, ..., m_d) \in S$ for some $m_1, ..., m_d \in \mathbb Z$. This is equivalent to $\sum_i y_i + mn = 0 \pmod k$ for some $m$. This in turn is equivalent to $\sum_i y_i = 0 \pmod{\gcd(k, n)}$.

So the answer to your original problem is $S_n = \{(y_1, ..., y_d) | \sum y_i = 0 \pmod{\gcd(k, n)}\}$. So the graph is connected iff $k$ and $n$ are co-prime.

So in the original case $n = 10$ and $d = 4$, we have the following. For $k = 2$, because $\gcd(2, 10) = 2$, the reachable states are those where sum of the lock numbers is even. For $k = 3$, because $\gcd(3, 10) = 1$, all lock states are reachable. For $k = d = 4$, only states where all digits are the same are reachable.