**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$?



Bike lock graph
**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.


