Return to Answer

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.

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.

TL;DR: the graph is connected iff $k < d$ and $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$. If $k = d$, then clearly $S = \{(x, ..., x) | x \in \mathbb Z\}$. So from now on, let's assume that $k < d$.

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 as follows. If $k = d$, then $S_n = \{(y, ..., y) | y \in Z_n\}$. If $k < d$, then $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.

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.

Note: the $n$ and $d$ are swapped in this answer, I'm rewriting it now.

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

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

Let's first consider this question in $\mathbb Z^n$ instead, and ask for the corresponding span $S$. If $k = n$, then clearly $S = \{(x, ..., x) | x \in \mathbb Z\}$. So from now on, let's assume that $k < n$.

For distinct $i_1, ..., i_k$, let $A(i_1, ..., i_k)$ be $(x_1, ..., x_n) \in \mathbb Z^n$ 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_n) \in \mathbb Z^n$ 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_n)$ of any $A(i_1, ..., i_k)$ sum to $k$. Therefore any $(x_1, ..., x_n) \in S$ satisfies $\sum x_i = 0 \pmod k$. We'll now show the reverse: any $(x_1, ..., x_n) \in \mathbb Z^n$ with $\sum x_i = 0 \pmod k$ belongs to $S$. We'll show this by starting from $(x_1, ..., x_n)$ 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_n)$ such that $\sum x_i = 0$. If $(x_1, ..., x_n) \neq (0, ..., 0)$, then we take some $x_i < 0$ and some $x_j > 0$, and add $B(i, j)$ to $(x_1, ..., x_n)$. 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_n)$ was in $S$.

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

So the answer to your original problem is as follows. If $k = n$, then $S_d = \{(y, ..., y) | y \in Z_d\}$. If $k < n$, then $S_d = \{(y_1, ..., y_n) | \sum y_i = 0 \pmod{\gcd(k, d)}\}$. So the graph is connected iff $k$ and $d$ are co-prime.

So in the original case $d = 10$ and $n = 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 = n = 4$, only states where all digits are the same are reachable.

TL;DR: the graph is connected iff $k < d$ and $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$. If $k = d$, then clearly $S = \{(x, ..., x) | x \in \mathbb Z\}$. So from now on, let's assume that $k < d$.

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 as follows. If $k = d$, then $S_n = \{(y, ..., y) | y \in Z_n\}$. If $k < d$, then $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.