Bike lock graph

Question

Motivation. I have a bike lock with 4 dials, and I was wondering whether I can reach any combination by always turning a fixed number $k$, say $k=2$, of the dials, by $1$ position, instead of just turning $1$ dial at the time, which makes for a boring challenge.

Formal version. For any integer $n>2$, let $[n] =\{1,\ldots, n\}$ and let $C_n = ([n], E_n)$ denote the cyclic graph on the vertex set $[n] =\{1,\ldots, n\}$ with $$E_n = \big\{\{k, k+1\}: 1\leq k < n\big\}\cup\big\{0,n\big\}.$$

Let $d$ denote the number of dials, $n$ the number of positions that any dial can take, and let $k\leq d$ be the fixed number of dials we have to turn by $1$ position at every step.

The dial itself can be represented by $[n]^d$. For $x,y\in[n]^d$ we let the differing set $D(x,y)$ to be defined by $\{i\in[d]: x_i\neq y_i\}$ where $x_i$ denotes the $i$th component of $x\in [n]^d$.

So we can define the following bike lock graph $B(n, d, k)$ for positive integers $n,d,k>1$ with $k\leq d$:

1. $V(B(n,d,k)) = [n]^d$,
2. $E(B(n,d, k)) = \big\{\{x,y\} \in [n]^d: |D(x,y)| = k \text{, and for all } i\in D(x,y)\text{ we have } \{x_i, y_i\}\in E_n\big\}.$

Every configuration of the bike lock can be reached with the allowed moves if and only if the corresponding graph $B(n,d,k)$ is connected.

Question. Are there infinitely many integers $n>1$ such given an integer $d>2$, the graph $B(n,d,k)$ is connected for some integer $k$ with $2\leq k\leq d-1$?

Answer 1

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.