19
$\begingroup$

A friend of mine asked me if it was possible - physical difficulties aside - to generate all 32 combinations of raised/lowered fingers by changing status of a fixed number of fingers at every step.

I immediately told him that with a single finger moved the solution is a Gray code, and that for parity reasons it was impossible to find a solution moving either 2 or 4 digits. I eventually found out a solution which moves three digits at a time, so that problem is solved.

But now I am wondering what would happen if I had more fingers. The proof involving parity remains valid; but do all other values have a solution?

$\endgroup$
7
  • 2
    $\begingroup$ Hint: Let me generalize. Instead of having $5$ fingers, you have $n$ fingers (thus $2^n$ possible combinations), and you are required to flip precisely $j$ fingers per step, where $j$ is a fixed odd integer such that $1\leq j \leq 2^n-1$. If you can find an invertible $\mathbb F_2$-linear map $u:\mathbb F_2^n \to \mathbb F_2^n$ which sends all vectors $\left(0,0,...,0,1,0,0,...0\right)$ to vectors with precisely $j$ nonzero coordinates each, then the problem is solved (because you can apply this map to the vectors of the Gray code). I am pretty sure that such a map should not be hard to find. $\endgroup$ Sep 2, 2013 at 13:39
  • 2
    $\begingroup$ Indeed, constructing such a map $u$ boils down to proving that there exist $n$ linearly independent vectors having precisely $j$ nonzero coordinates each. In other words, this means showing that the vectors in $\mathbb F_2^n$ having precisely $j$ nonzero coordinates each span $\mathbb F_2^n$. This can be done as follows: It is clear that all vectors having precisely $2$ nonzero coordinates are in their span (because you can get any such vector as a difference of two vectors with precisely $j$ nonzero coordinates each). Now, if you start with a vector having $j$ nonzero coordinates ... $\endgroup$ Sep 2, 2013 at 13:45
  • 2
    $\begingroup$ ... and subtract $\dfrac{j-1}{2}$ vectors having $2$ nonzero coordinates each, then you end up with a vector having only one nonzero coordinate (if you have chosen the right vectors to subtract), and you can get each of the basis vectors this way. Hence, you are done. $\endgroup$ Sep 2, 2013 at 13:46
  • 1
    $\begingroup$ @darijgrinberg Seven years later, I have to ask - have you finished writing the answer? :) $\endgroup$ Sep 5, 2020 at 6:34
  • 1
    $\begingroup$ @VarunVejalla: And two more years later, here it is :) $\endgroup$ Apr 24, 2022 at 20:25

1 Answer 1

2
$\begingroup$

I have just used this question as a homework problem in my graph theory course, so I ended up writing a solution.

First, some notations (from Lecture 6 in this course):

Definition. Let $G$ be a simple graph. A Hamiltonian cycle in $G$ means a cycle $\left( v_0 ,v_1 ,\ldots,v_k \right)$ of $G$ such that each vertex of $G$ appears exactly once among $v_0 ,v_1 ,\ldots,v_{k-1}$. We abbreviate the word "Hamiltonian cycle" as "hamc".

Definition. Let $n\in\mathbb{N}$. The $n$-hypercube graph $Q_n$ is the simple graph with vertex set \begin{align*} \left\{ 0,1\right\} ^n = \left\{ \left( a_1 ,a_2 ,\ldots,a_n \right) \ \mid\ \text{each }a_{i}\text{ belongs to } \left\{ 0, 1 \right\} \right\} \end{align*} and with the edge set that is defined as follows: A vertex $\left( a_1 ,a_2 ,\ldots,a_n \right) \in\left\{ 0,1\right\} ^n $ is adjacent to a vertex $\left( b_1 ,b_2 ,\ldots,b_n \right) \in\left\{ 0,1\right\} ^n $ if and only if there exists exactly one $i\in\left\{ 1,2,\ldots ,n\right\} $ such that $a_{i}\neq b_{i}$. (For example, in $Q_{4}$, the vertex $\left( 0,1,1,0\right) $ is adjacent to $\left( 0,1,0,0\right) $.)

The elements of $\left\{ 0,1\right\} ^n $ are often called bitstrings (or binary words), and their entries are called their bits (or letters). Thus, the vertices of $Q_n$ are the bitstrings that have $n$ bits; two bitstrings are adjacent in $Q_n$ if and only if they differ in exactly one bit.

We often write a bitstring $\left( a_1 ,a_2 ,\ldots,a_n \right) $ as $a_1 a_2 \cdots a_n$. (For example, we write $\left( 0,1,1,0\right) $ as $0110$.)

Theorem 1 (existence of Gray codes). Let $n\geq2$. Then, the graph $Q_n$ has a hamc.

Proof. See Theorem 1.2.9 in Lecture 6, or the Wikipedia page on Gray codes. $\blacksquare$

Now, here is your question rewritten as an exercise in graph theory ($n$ is the total number of fingers, and $k$ is the number of fingers that get flipped in each step):

Exercise. Let $n$ and $k$ be two integers such that $n>k>0$. Define the simple graph $Q_{n,k}$ as follows:

  • Its vertices are the bitstrings $\left( a_1 ,a_2 ,\ldots,a_n \right) \in\left\{ 0,1\right\} ^n $.

  • Two such bitstrings are adjacent (as vertices) if and only if they differ in exactly $k$ bits. (In other words: Two vertices $\left( a_1 ,a_2 ,\ldots,a_n \right) $ and $\left( b_1 ,b_2 ,\ldots,b_n \right) $ are adjacent if and only if the number of $i\in\left\{ 1,2,\ldots,n\right\} $ satisfying $a_{i}\neq b_{i}$ equals $k$.)

(Thus, $Q_{n,1}$ is the $n$-hypercube graph $Q_n$.)

(a) Show that $Q_{n,k}$ has no hamc when $k$ is even.

(b) Show that $Q_{n,k}$ has a hamc when $k$ is odd.

Solution. (a) Assume that $k$ is even. We call a bitstring $\left( a_1 ,a_2 ,\ldots,a_n \right) $ even if its sum $a_1 +a_2 +\cdots +a_n$ is even, and we call it odd otherwise. If we change a single bit in a bitstring, then its "parity" gets flipped (i.e., it becomes odd if it was even, and it becomes even if it was odd), since its sum changes by exactly $1$. Thus, if we change exactly $k$ bits in a bitstring, then its "parity" does not change (i.e., it remains even if it was even, and it remains odd if it was odd), because $k$ is even. Hence, any edge of $Q_{n,k}$ either joins two even bitstrings or joins two odd bitstrings; but it cannot join an even bitstring with an odd bitstring. Therefore, a path of $Q_{n,k}$ cannot connect an even bitstring with an odd bitstring either (because such a path would necessarily have an edge that joins an even bitstring with an odd bitstring). Since $Q_{n,k}$ has both even bitstrings and odd bitstrings, this entails that the graph $Q_{n,k}$ is not connected. Thus, the graph $Q_{n,k}$ cannot have a hamc (because a hamc would render it connected). This solves part (a) of the exercise.

(b) Assume that $k$ is odd.

We consider the field $\mathbb{F}_2$ with two elements. We shall identify the set $\left\{ 0,1\right\}$ with this field $\mathbb{F}_2$. The bitstrings $\left( a_1 ,a_2 ,\ldots,a_n \right) \in\left\{ 0,1\right\} ^n$ thus become the size-$n$ row vectors in the $\mathbb{F}_2$-vector space $\mathbb{F}_2^n$. Let $e_1 ,e_2 ,\ldots,e_n$ be the standard basis vectors of $\mathbb{F}_2^n$ (that is, let \begin{align*} e_{i}:=\left( \underbrace{0,0,\ldots,0}_{i-1\text{ zeroes}} ,1,\underbrace{0,0,\ldots,0}_{n-i\text{ zeroes}}\right) \in\mathbb{F}_2^n \end{align*} for each $i\in\left\{ 1,2,\ldots,n\right\}$). We furthermore define a $k$-finger vector to be a vector in $\mathbb{F}_2^n$ that has exactly $k$ nonzero entries. Thus, a $k$-finger vector is the same thing as a sum of $k$ distinct standard basis vectors -- i.e., a vector of the form $e_{i_1 } + e_{i_2} + \cdots + e_{i_k}$ for some $1\leq i_1 <i_2 <\cdots<i_k \leq n$. In particular, the $1$-finger vectors are precisely the standard basis vectors.

The definitions of the graphs $Q_n$ and $Q_{n,k}$ can now be easily rewritten in terms of the vectors we have just defined:

  • Two vectors $x\in\mathbb{F}_2^n $ and $y\in\mathbb{F}_2^n $ are adjacent as vertices of the $n$-hypercube graph $Q_n$ if and only if their difference $x-y$ is one of the standard basis vectors $e_1 ,e_2 ,\ldots,e_n$.

  • Two vectors $x\in\mathbb{F}_2^n $ and $y\in\mathbb{F}_2^n $ are adjacent as vertices of the graph $Q_{n,k}$ if and only if their difference $x-y$ is a $k$-finger vector.

Now, we recall that linear algebra over the field $\mathbb{F}_2$ works exactly like linear algebra over the real numbers (or over the complex numbers), as long as we stick to the "purely linear" topics (such as linear dependence, basis, spans, etc.). In particular, $n$ linearly independent vectors in $\mathbb{F}_2^n$ always form a basis of $\mathbb{F}_2^n$ (since $\mathbb{F}_2^n$ is an $n$-dimensional vector space over $\mathbb{F}_2$).

Let $S$ be the span of all $k$-finger vectors in $\mathbb{F}_2^n$. We shall show that $S$ is the entire space $\mathbb{F}_2^n$. Indeed:

  • The vector $e_1 -e_2 $ belongs to $S$, since it is the difference of the two $k$-finger vectors $e_1 +\underbrace{e_{3}+e_{4}+\cdots+e_{k+1}}_{\text{sum of all }e_{i}\text{ with }3\leq i\leq k+1}$ and $e_2 + e_3 + \cdots + e_{k+1}$. Since subtraction and addition are the same operation over the field $\mathbb{F}_2$, we can restate this as follows: The vector $e_1 +e_2$ belongs to $S$.

  • Similarly, the vectors $e_{3}+e_{4}$ and $e_{5}+e_{6}$ and $e_{7}+e_{8}$ and so on belong to $S$ as well.

  • The vector $e_k $ belongs to $S$, since it is the difference \begin{align*} \underbrace{\left( e_1 +e_2 +\cdots+e_k \right) }_{\substack{\in S\\\text{(since this is a }k\text{-finger vector)}}}-\underbrace{\left( e_1 +e_2 \right) }_{\substack{\in S\\\text{(by the previous}\\\text{bullet point)}}}-\underbrace{\left( e_{3}+e_{4}\right) }_{\substack{\in S\\\text{(by the previous}\\\text{bullet point)}}}-\cdots-\underbrace{\left( e_{k-2}+e_{k-1}\right) }_{\substack{\in S\\\text{(by the previous} \\\text{bullet point)}}} \end{align*} (here we are using the assumption that $k$ is odd).

  • Similarly, each standard basis vector $e_{i}$ (with $i\in\left\{ 1,2,\ldots,n\right\} $) belongs to $S$.

  • But this implies that $S=\mathbb{F}_2^n$ (since $S$ is a vector subspace of $\mathbb{F}_2^n$).

This quickly entails that we can find $n$ linearly independent $k$-finger vectors in $\mathbb{F}_2^n$.

[Proof: For any subset $T$ of $\mathbb{F}_2^n$, we let $\operatorname{span} T$ denote the ($\mathbb{F}_2$-linear) span of $T$. Let $L$ be a maximum-size linearly independent set of $k$-finger vectors. Then, every $k$-finger vector lies in $\operatorname{span} L$ (since otherwise, we could add it to $L$, and would obtain a larger linearly independent set of $k$-finger vectors; but this would contradict the maximality of $L$). Hence, the span of all $k$-finger vectors is a subset of $\operatorname{span} L$ (since $\operatorname{span} L$ is closed under linear combination). In other words, $S$ is a subset of the span of $L$ (since $S$ is the span of all $k$-finger vectors). Hence, $\dim S \leq \dim \left( \operatorname{span} L\right) = \left|L\right|$ (since the set $L$ is linearly independent, and thus is a basis of its span). However, we know that $S = \mathbb{F}_2^n$, so that $\dim S = \dim\left(\mathbb{F}_2^n\right) = n$. Thus, $n = \dim S \leq \left|L\right|$. Hence, we can find $n$ distinct elements of $L$. Therefore, we can find $n$ linearly independent $k$-finger vectors (since all elements of $L$ are $k$-finger vectors). Qed.]

So we can find $n$ linearly independent $k$-finger vectors. Let $f_1 ,f_2 ,\ldots,f_n$ be such $n$ vectors. Then, $\left( f_1 ,f_2 ,\ldots,f_n \right) $ is a basis of the $\mathbb{F}_2 $-vector space $\mathbb{F}_2^n $ (since any $n$ linearly independent vectors in $\mathbb{F}_2^n $ form a basis). Therefore, there exists a vector space isomorphism (i.e., an invertible $\mathbb{F}_2 $-linear map) $\Phi :\mathbb{F}_2^n \to \mathbb{F}_2^n $ that sends the standard basis vectors $e_1 ,e_2 ,\ldots,e_n$ to $f_1 ,f_2 ,\ldots,f_n$, respectively. (This isomorphism $\Phi$ is the map that sends each vector $\left( \lambda_1 ,\lambda_2 ,\ldots,\lambda_n \right) \in\mathbb{F} _2^n $ to the linear combination $\lambda_1 f_1 +\lambda_2 f_2 +\cdots+\lambda_n f_n$.) Consider this $\Phi$. Thus, $\Phi$ is an invertible linear map from $\mathbb{F}_2^n $ to $\mathbb{F}_2^n $ (since $\Phi$ is a vector space isomorphism). In particular, $\Phi$ is invertible, thus injective and surjective.

From $n>k>0$, we obtain $n\geq2$. Hence, Theorem 1 shows that the graph $Q_n$ has a hamc. Consider such a hamc, and denote it by $\left( g_0 ,g_1 ,g_2 ,\ldots,g_{2^n }\right) $ (so that $g_{2^n }=g_0 $). Thus, $g_0 ,g_1 ,g_2 ,\ldots,g_{2^n -1}$ are all the $2^n $ bitstrings, i.e., all the $2^n $ elements of $\mathbb{F}_2^n $. Moreover, any two consecutive entries $g_{m-1}$ and $g_{m}$ of this hamc differ in exactly $1$ bit (since $g_{m-1}g_{m}$ is an edge of the graph $Q_n$); in other words, their difference $g_{m}-g_{m-1}$ is a standard basis vector $e_{i}$.

Now, consider the tuple $\left( \Phi\left( g_0 \right) ,\Phi\left( g_1 \right) ,\Phi\left( g_2 \right) ,\ldots,\Phi\left( g_{2^n }\right) \right) $. The entries $\Phi\left( g_{m}\right) $ of this tuple are bitstrings in $\mathbb{F}_2^n $. Furthermore, the difference between any two consecutive entries $\Phi\left( g_{m-1}\right) $ and $\Phi\left( g_{m}\right) $ is \begin{align*} \Phi\left( g_{m}\right) -\Phi\left( g_{m-1}\right) & =\Phi\left( g_{m}-g_{m-1}\right) \ \ \ \ \ \ \ \ \ \ \left( \text{since }\Phi\text{ is a linear map}\right) \\ & =\Phi\left( e_{i}\right) \ \ \ \ \ \ \ \ \ \ \text{for some }i\in\left\{ 1,2,\ldots,n\right\} \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left( \begin{array} [c]{c} \text{since the difference }g_{m}-g_{m-1}\text{ is}\\ \text{a standard basis vector }e_{i} \end{array} \right) \\ & =f_{i}\ \ \ \ \ \ \ \ \ \ \left( \text{since }\Phi\text{ sends } e_1 ,e_2 ,\ldots,e_n \text{ to }f_1 ,f_2 ,\ldots,f_n \right) , \end{align*} and this is a $k$-finger vector (since $f_1 ,f_2 ,\ldots,f_n$ are $k$-finger vectors). In other words, any two consecutive entries $\Phi\left( g_{m-1}\right) $ and $\Phi\left( g_{m}\right) $ of the tuple $\left( \Phi\left( g_0 \right) ,\Phi\left( g_1 \right) ,\Phi\left( g_2 \right) ,\ldots,\Phi\left( g_{2^n }\right) \right) $ differ in exactly $k$ bits. Hence, this tuple $\left( \Phi\left( g_0 \right) ,\Phi\left( g_1 \right) ,\Phi\left( g_2 \right) ,\ldots,\Phi\left( g_{2^n }\right) \right) $ is a walk of the graph $Q_{n,k}$. Moreover, this walk is closed (since $g_{2^n }=g_0 $ and thus $\Phi\left( g_{2^n }\right) =\Phi\left( g_0 \right) $).

However, we know that the tuple $\left( g_0 ,g_1 ,g_2 ,\ldots,g_{2^n }\right) $ is a hamc. Thus, each vertex of $Q_n$ appears exactly once among its first $2^n $ entries $g_0 ,g_1 ,g_2 ,\ldots,g_{2^n -1}$ (by the definition of a hamc). In other words, the vertices $g_0 ,g_1 ,g_2 ,\ldots,g_{2^n -1}$ are distinct and satisfy $\mathbb{F}_2^n =\left\{ g_0 ,g_1 ,g_2 ,\ldots,g_{2^n -1}\right\} $ (since $\mathbb{F}_2^n $ is the set of vertices of $Q_n$). Consequently, the vertices $\Phi\left( g_0 \right) ,\Phi\left( g_1 \right) ,\Phi\left( g_2 \right) ,\ldots,\Phi\left( g_{2^n -1}\right) $ are distinct (since they are the images of the distinct vertices $g_0 ,g_1 ,g_2 ,\ldots,g_{2^n -1}$ under the injective map $\Phi$) and satisfy \begin{align*} \mathbb{F}_2^n & =\Phi\left( \mathbb{F}_2^n \right) \ \ \ \ \ \ \ \ \ \ \left( \text{since }\Phi\text{ is surjective}\right) \\ & =\Phi\left( \left\{ g_0 ,g_1 ,g_2 ,\ldots,g_{2^n -1}\right\} \right) \ \ \ \ \ \ \ \ \ \ \left( \text{since }\mathbb{F}_2^n =\left\{ g_0 ,g_1 ,g_2 ,\ldots,g_{2^n -1}\right\} \right) \\ & =\left\{ \Phi\left( g_0 \right) ,\Phi\left( g_1 \right) ,\Phi\left( g_2 \right) ,\ldots,\Phi\left( g_{2^n -1}\right) \right\} . \end{align*} In other words, the vertices $\Phi\left( g_0 \right) ,\Phi\left( g_1 \right) ,\Phi\left( g_2 \right) ,\ldots,\Phi\left( g_{2^n -1}\right) $ are distinct and form the set $\mathbb{F}_2^n $. In other words, each element of $\mathbb{F}_2^n $ appears exactly once among the vertices $\Phi\left( g_0 \right) ,\Phi\left( g_1 \right) ,\Phi\left( g_2 \right) ,\ldots,\Phi\left( g_{2^n -1}\right) $. In other words, each vertex of $Q_{n,k}$ appears exactly once among the vertices $\Phi\left( g_0 \right) ,\Phi\left( g_1 \right) ,\Phi\left( g_2 \right) ,\ldots,\Phi\left( g_{2^n -1}\right) $ (since the elements of $\mathbb{F}_2^n $ are the vertices of $Q_{n,k}$). Thus, the closed walk $\left( \Phi\left( g_0 \right) ,\Phi\left( g_1 \right) ,\Phi\left( g_2 \right) ,\ldots,\Phi\left( g_{2^n }\right) \right) $ is a hamc of $Q_{n,k}$ (by the definition of a hamc). Hence, $Q_{n,k}$ has a hamc. This solves part (b) of the problem. $\blacksquare$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .