Problem of the Month
Solution to Problem 7: April 2023

1. Suppose $\mathit{a}$ and $\mathit{b}$ are elements in $A_n$ and that $d(\mathit{a},\mathit{b})=k$ for some $k$. If $k=0$, then $\mathit{a}=\mathit{b}$, so their distance in the graph is also $0$.

   Otherwise, $\mathit{a}$ and $\mathit{b}$ differ at exactly $k$ coordinates $i_1,i_2,\dots ,i_k$ where $i_1<i_2<\cdots <i_k$. Using the notation introduced in the problem statement, we mean that $\mathit{a}[i]\ne \mathit{b}[i]$ if $i$ is in the list $i_1,i_2,\dots ,i_k$ and $\mathit{a}[i]=\mathit{b}[i]$ otherwise. Notice that the function $g(x)=1-x$ has the property that $g(0)=1$ and $g(1)=0$, so $g$ switches $1$ and $0$. We will now define a sequence ${\mathit{a}}_1,{\mathit{a}}_2,\dots ,{\mathit{a}}_k$ of elements in $A_n$. Informally, ${\mathit{a}}_1$ is obtained from $\mathit{a}$ by leaving all coordinates alone except $\mathit{a}[i_1]$, which gets changed from $0$ to $1$ or $1$ to $0$ as appropriate. Continuing, ${\mathit{a}}_2$ is obtained from ${\mathit{a}}_1$ by leaving all coordinates alone except ${\mathit{a}}_1[i_2]$, which gets switched, and this continues for ${\mathit{a}}_3$, ${\mathit{a}}_4$, and so on. More formally, for each $m\ge 1$ with $1\le m\le k$ we define ${\mathit{a}}_m$ as follows.

   • ${\mathit{a}}_m[i]=\mathit{a}[i]$ if $i$ is not in the list $i_1,i_2,\dots ,i_k$.

   • ${\mathit{a}}_m[i]=g(\mathit{a}[i])$ for each $i$ in the list $i_1,i_2,\dots ,i_m$.

   • ${\mathit{a}}_m[i]=\mathit{a}[i]$ for each $i$ in the list $i_{m+1},i_{m+2},\dots ,i_k$.

   By construction, the list $\mathit{a},{\mathit{a}}_1,{\mathit{a}}_2,\dots ,{\mathit{a}}_{k-1},{\mathit{a}}_k$ is a list in which every pair of elements differ at exactly one coordinate. Moreover, the list is that which is generated by changing the coordinates of $\mathit{a}$ that differ from those of $\mathit{b}$ one at a time, from leftmost to rightmost. This means $\mathit{b}={\mathit{a}}_k$, and the above is a walk from $\mathit{a}$ to $\mathit{b}$. There are $k+1$ vertices in this walk, so there are $k$ edges.

   We have constructed a walk from $\mathit{a}$ to $\mathit{b}$ in the natural graph of $A_n$ that has length $k$, which means the distance from $\mathit{a}$ to $\mathit{b}$ in the natural graph is at most $k$. To see that it is at least $k$, we suppose $\mathit{a},{\mathit{c}}_1,{\mathit{c}}_2,\dots ,{\mathit{c}}_{m-1},\mathit{b}$ is a walk in the natural graph of $A_n$ of length $m$ for some $m$. Since there are $m$ vertices in this walk in addition to $\mathit{a}$ and two vertices have an edge between them exactly when they differ at exactly one coordinate, the total number of coordinates at which $\mathit{a}$ and $\mathit{b}$ (the ends of the walk) can differ is at most $m$. Since we know that they differ at exactly $k$ coordinates, we must have that $m\ge k$. This means that any walk from $\mathit{a}$ to $\mathit{b}$ in the natural graph of $A_n$ has at least $k$ edges.

   We have shown that the distance in the natural graph between $\mathit{a}$ and $\mathit{b}$ is at least $k$ and at most $k$, which means it is exactly $k$.

2. For convenience, in the solution to this part and the solution to part (c), we will refer to a two element subset as a pair. Since $d(\mathit{a},\mathit{b})=d(\mathit{b},\mathit{a})$ for any elements $\mathit{a},\mathit{b}\in A_n$, we will say that $d(\mathit{a},\mathit{b})$ is the Hamming distance of the pair $\{\mathit{a},\mathit{b}\}$ or the pair $\{\mathit{a},\mathit{b}\}$ has Hamming distance $d(\mathit{a},\mathit{b})$, and possibly other similar things depending on the grammar in that particular sentence. Similarly, we might say that $\{\mathit{a},\mathit{b}\}$ has distance $k$ in a graph to mean that the distance between the vertices labelled by $\mathit{a}$ and $\mathit{b}$ is $k$ in that graph.

   For a fixed element $\mathit{a}\in A_n$, an element $\mathit{b}\in A_n$ satisfies $d(\mathit{a},\mathit{b})=k$ exactly when it differs from $\mathit{a}$ at exactly $k$ coordinates. There are $n$ coordinates in total, so there are ${\displaystyle (\genfrac{}{}{0ex}{}{n}{k})}$ possible choices of $k$ coordinates that could be different from $\mathit{a}$. Therefore, for a fixed element $\mathit{a}\in A_n$, there are exactly ${\displaystyle (\genfrac{}{}{0ex}{}{n}{k})}$ elements $\mathit{b}\in A_n$ with the property that $d(\mathit{a},\mathit{b})=k$. There are $2^n$ elements in $A_n$ and each $\mathit{a}\in A$ belongs to exactly ${\displaystyle (\genfrac{}{}{0ex}{}{n}{k})}$ pairs with a Hamming distance of $k$. This gives a total of $2^n\times {\displaystyle (\genfrac{}{}{0ex}{}{n}{k})}$ pairs. However, this total

   counts every pair twice, once for each of its two elements. Thus, the number of pairs in $A_n$ with a Hamming distance of $k$ is ${\displaystyle \frac{1}{2}}{2}^n{\displaystyle (\genfrac{}{}{0ex}{}{n}{k})}=2^{n-1}{\displaystyle (\genfrac{}{}{0ex}{}{n}{k})}$.

3. Denote by $E_n$ the set of pairs $\{\mathit{a},\mathit{b}\}$ from $A_n$ satisfying $d(\mathit{a},\mathit{b})=1$. From part (b), there are $2^{n-1}{\displaystyle (\genfrac{}{}{0ex}{}{n}{1})}=n{2}^{n-1}$ pairs in $E_n$. In the relabelled natural graph of $A_n$, we want the distances of the pairs in $E_n$ to be equally distributed among all possible distances in the graph. There are $n$ possible distances between distinct vertices in the graph, so the fact that $n{2}^{n-1}$ is a multiple of $n$ is a good sign.

   We want to permute the elements of $A_n$ in such a way that for each $k$ from $1$ through $n$, exactly ${\displaystyle \frac{n{2}^{n-1}}{n}}=2^{n-1}$ pairs in $E_n$ have a distance of $k$ in the relabelled graph.

   There are many ways to do this. The approach given here is inductive, starting by examining $A_2$. Consider the example from the problem statement. In that example, $01$ and $11$ were switched and $00$ and $10$ stayed the same.

   

   Although it is not very interesting in $A_2$, there is an observation we can make that will generalize. The vertices that are connected by horizontal edges in the diagram of the natural graph of $A_2$ remain connected by an edge after permuting. The vertices in the top change order but their distance apart does not change. Meanwhile, the vertices that are connected by a vertical edge are moved to occupy opposite corners of the square so their distance goes from $1$ to $2$. While this is only an increase of $1$, it will be useful going forward to think of the vertices connected by vertical edges as having gone from as close together as possible (connected by an edge) to as far apart as possible.

   Now consider the natural graph of $A_3$, which is pictured below.

   

   There are $12$ edges in the graph. After permuting the labels of the graph, we want ${\displaystyle \frac{12}{3}}=4$ pairs of adjacent vertices to be sent to adjacent vertices, $4$ pairs of adjacent vertices to be sent to vertices with a distance of $2$, and $4$ pairs of adjacent vertices to be sent to vertices with a distance of $3$.

   Looking at the diagram, we can think of the natural graph of $A_3$ as being composed of two copies of the natural graph of $A_2$ laid horizontally on top of each other. The labelling also has some coherence with the labelling of $A_2$. First, label the bottom and top square as if they were copies of the natural graph of $A_2$, making sure to label vertically-adjacent vertices in the same way. Next, append a $0$ to the right of every label in the bottom layer and append a $1$ to the right of every label in the top layer.

   To permute the labels in the way we want, we will first perform the same permutation on each layer as we did in $A_2$. In each layer, this moves two pairs of labels from adjacent vertices so that they are at a distance of $2$. There are also two pairs of adjacent vertices in each layer that remain adjacent after permuting. The four pairs of vertically-adjacent vertices will remain vertically adjacent because we will have performed the exact same permutation in each layer. At this point, the labels on four pairs of adjacent vertices have been sent to vertices that are $2$ apart and the other $8$ pairs of labels remain on adjacent vertices. The diagram below shows what we have done so far:

   

   The second and final step is to swap the corners in the top layer. This will have the effect of moving the labels on vertically-adjacent vertices to be as far apart as possible. In a "cube", this means they will end up at opposite ends of a "space diagonal". Swapping the corners in a layer preserves the distance between all pairs of vertices in that layer. This means the net effect of the second step is to move four pairs of adjacent vertices so that they are at a distance of $3$. The overall effect is shown below:

   

   In the table below, the first column has the $12$ pairs from $E_3$ and the second column has the distance of the corresponding pair in the relabelled graph.

   $\{\mathit{a},\mathit{b}\}$	new distance
   $\{000,001\}$	$3$
   $\{000,010\}$	$2$
   $\{000,100\}$	$1$
   $\{001,011\}$	$2$
   $\{001,101\}$	$1$
   $\{010,011\}$	$3$
   $\{010,110\}$	$1$
   $\{011,111\}$	$1$
   $\{100,101\}$	$3$
   $\{100,110\}$	$2$
   $\{101,111\}$	$2$
   $\{110,111\}$	$3$

   As $n$ grows, the natural graph of $A_n$ gets harder and harder to draw in a useful way, so we need some notation to help translate the geometric idea into symbols. First, we will clarify what we actually want.

   Suppose $f$ is a function with domain $A_n$ and codomain $A_n$. This means $f$ is a function that takes elements of $A_n$ as input and also outputs elements of $A_n$. When we talk about a permutation of $A_n$, we really mean a function $f$ with domain and codomain both equal to $A_n$ that is a bijection. For a brief discussion about what a bijection is, you can consult Appendix 1 from the solution to the February 2023 problem. In the context of this solution, a function from $A_n$ to $A_n$ is a permutation if every possible output is attained by exactly one input. For example, the function $f$ with domain and codomain $A_2$ given by $$\begin{array}{rl}f(00)& =11\\ f(01)& =01\\ f(10)& =00\\ f(11)& =10\end{array}$$ is a bijection from $A_2$ to $A_2$. Every possible output is attained (the four elements of $A_2$ appear on the right side of the displayed equations above) and no output is attained more than once. If you think about it, every way to order the elements of $A_2$ (a permutation) corresponds to exactly one such function: choose an order of the elements, then write them in that order in the second column above. It will not be important for this solution, but it might help you to understand this connection if you convince yourself that there are exactly $4!=24$ bijections from $A_2$ to itself.

   A rearrangement of the labels in the natural graph of $A_n$ can be thought of as a bijection from $A_n$ to itself. If $f$ is such a function, then $f(\mathit{a})$ is equal to the original label of the vertex to which the label $\mathit{a}$ is sent by the permutation. For example, the permutation for $A_3$ corresponding to the relabelling from earlier (shown below)

   

   is given by $$\begin{array}{rl}f(000)& =000\\ f(001)& =111\\ f(010)& =110\\ f(011)& =001\\ f(100)& =100\\ f(101)& =011\\ f(110)& =010\\ f(111)& =101\end{array}$$ For example, the fourth of the displayed equations above is $f(011)=001$ because in the second diagram $011$ appears where $001$ originally appeared.

   This is an important observation because we can now recognize distance in the relabelled graph as a Hamming distance. The distance between $\mathit{a}$ and $\mathit{b}$ in the relabelled graph is equal to the distance between $f(\mathit{a})$ and $f(\mathit{b})$ in the original graph. By part (a), this means the distance between $\mathit{a}$ and $\mathit{b}$ in the relabelled graph is equal to $d(f(\mathit{a}),f(\mathit{b}))$.

   We can now formally articulate what we seek. For each $n$, we would like a function $f_n$ with domain and codomain both equal to $A_n$ with the following properties.

   • $f_n$ is a permutation of $A_n$ (a bijection).

   • Among the $n{2}^{n-1}$ pairs $\{\mathit{a},\mathit{b}\}$ from $E_n$, $d(f_n(\mathit{a}),f_n(\mathit{b}))$ takes on each value from $1$ through $n$ exactly $2^{n-1}$ times.

   It may be a good idea to digest what has been said so far, possibly going back to see how this applies to $A_2$ and $A_3$.

   We can now define $f_n$ for each $n$, but the definition will be recursive, so we need a bit more notation. For an element $\mathit{a}$ in $A_n$ where $n\ge 1$, we will write $\mathit{a}|0$ to mean the element of $A_{n+1}$ that is obtained by appending a $0$ to the right end of $\mathit{a}$. For example, $00110|0=001100$. Similarly, $\mathit{a}|1$ is the element of $A_{n+1}$ obtained by appending $1$ to the right end of $\mathit{a}$. Also, we will denote by $\bar{\mathit{a}}$ the element of $A_n$ obtained by changing every coordinate of $\mathit{a}$ from $0$ to $1$ or $1$ to $0$, as appropriate. For example, if $\mathit{a}=0010111$, then $\bar{\mathit{a}}=1101000$.

   Starting with $n=1$ (which we have not addressed up to this point) we will let $f_1(\mathit{a})=\mathit{a}$. That is, $f_1(\mathit{a})$ is the identity function. The elements of $A_1$ are $0$ and $1$, and $f_1(0)=0$ and $f_1(1)=1$. We now continue recursively. For $n\ge 1$, we define $f_{n+1}$ from $f_n$ as follows.

   • If $\mathit{a}\in A_{n+1}$ is of the form $\mathit{b}|0$ for some $\mathit{b}\in A_n$, then $f_{n+1}(\mathit{a})=f_n(\mathit{b})|0$.

   • If $\mathit{a}\in A_{n+1}$ is of the form $\mathit{b}|1$ for some $\mathit{b}\in A_n$, then $f_{n+1}(\mathit{a})=\overline{f_n(\mathit{b})}|1$.

   Notice that the above instructions indeed explain how to evaluate $f_{n+1}$ at every element of $A_{n+1}$ because each element of $A_{n+1}$ can be constructed in exactly one way by appending either a $0$ or a $1$ to the right of an element from $A_n$. As an example, we will determine exactly what $f_2$ does to each element in $A_2$. For $00$, we have to use the rule in the first bullet point because the rightmost digit is $0$. $f_1(0)=0$, so we have that $f_2(00)=00$. Since the second digit of $10$ is also $0$ and $f_1(1)=1$, we get that $f_2(10)=10$. For $01$, we have to use the rule in the second bullet point. This means $f_2(01)=\overline{f_1(0)}|1=\bar{0}|1=11$. Finally, $f_2(11)=\overline{f_1(1)}|1=\bar{1}|1=01$. This is exactly the function from $A_2$ to itself discussed earlier. We leave it as an exercise to verify that $f_3$ is exactly the permutation of $A_3$ discussed earlier.

   We can now prove by induction that $f_n$ does what we want for every $n$. Before doing that, we will discuss how this function corresponds to the geometric idea from earlier. The elements in $A_{n+1}$ can be obtained by taking each element of $A_n$ and appending a $0$ to the right and a $1$ to the right, in a way getting two elements in $A_{n+1}$ from every element in $A_n$. By this reasoning, $A_{n+1}$ can be thought of as two copies of $A_n$: elements ending in $0$ and elements ending in $1$. If you look at the natural graph of $A_3$ above, these two copies are exactly the "bottom" and the "top" squares. The way $f_{n+1}$ is defined is to operate differently on the two copies of $A_n$, since how $f_{n+1}(\mathit{a})$ is computed depends on the rightmost digit of $\mathit{a}$. In other words, it depends on which copy of $A_n$ $\mathit{a}$ belongs to. If $\mathit{a}$ has a rightmost digit of $0$, then $f_{n+1}$ essentially does what $f_n$ did. This corresponds to the bottom face of the cube being permuted exactly as the square was. If the rightmost digit of $\mathit{a}$ is $1$, then $\mathit{a}$ is in the other copy, corresponding to the top face of the cube in the case of $A_3$. In this situation, we apply $f_n$ to the element of $A_n$ obtained by removing the last digit, just as we would if the rightmost digit were $0$. However, we then switch every digit, and this corresponds to "swapping the diagonals" in $A_3$. Finally, a $1$ is appended to the right of the result, which corresponds to making sure that elements in the top of the cube stay in the top of the cube during the permutation.

   For $n=1$, it is an exercise in understanding definitions to see that $f_n$ satisfies the given conditions. We have already established this for $n=2$, and $n=3$ can be verified by confirming that $f_3$ is exactly the permutation from earlier that we verified worked.

   We now assume, for some $n\ge 1$, that $f_n$ is a permutation of $A_n$ with the property that among pairs $\{\mathit{a},\mathit{b}\}$ from $E_n$, $d(f_n(\mathit{a}),f_n(\mathit{b}))$ takes on every value from $1$ through $n$ exactly $2^{n-1}$ times. We will show that $f_{n+1}$ is a permutation of $A_{n+1}$ with the property that among pairs $\{\mathit{a},\mathit{b}\}$ from $E_{n+1}$, $d(f_{n+1}(\mathit{a}),f_{n+1}(\mathit{b}))$ takes on every value from $1$ through $n+1$ exactly $2^n$ times.

   To see that $f_{n+1}$ is a permutation, let $\mathit{a}\in A_n$ be arbitrary. Since $f_n$ is a permutation, there is a unique element $\mathit{b}\in A_n$ such that $f_n(\mathit{b})=\mathit{a}$ and a unique element $\mathit{c}\in A_n$ such that $f_n(\mathit{c})=\bar{\mathit{a}}$. Using the definition of $f_{n+1}$, we have $f_{n+1}(\mathit{b}|0)=f_n(\mathit{b})|0=\mathit{a}|0$ and $f_{n+1}(\mathit{c}|1)=\overline{f_n(\mathit{c})}|1=\overline{\stackrel{―}{a}}|1=\mathit{a}|1$. Since every element in $A_{n+1}$ is of the form $\mathit{a}|0$ or $\mathit{a}|1$ for some $\mathit{a}\in A_n$, we have shown that every element of $A_{n+1}$ is in the range of $f_{n+1}$. Now suppose ${\mathit{a}}_1,{\mathit{a}}_2,{\mathit{a}}_3,\dots ,{\mathit{a}}_{2^{n+1}}$ are the elements of $A_{n+1}$ (in some order). We have shown that every element of $A_{n+1}$ appears in the list $$f_{n+1}({\mathit{a}}_1),f_{n+1}({\mathit{a}}_2),\dots ,f_{n+1}({\mathit{a}}_{2^{n+1}})$$ at least once. There are $2^{n+1}$ elements in the list above and $2^{n+1}$ elements in $A_{n+1}$, so every element of $A_{n+1}$ must appear in the list above exactly once. In other words, $f_{n+1}$ is a permutation of $A_{n+1}$.

   To prove the other fact about $f_{n+1}$, we will use the fact that $d(\mathit{a},\mathit{b})=d(\bar{\mathit{a}},\bar{\mathit{b}})$ for any $\mathit{a}$ and $\mathit{b}$. It is left as an exercise to verify this.

   Suppose $k$ is a positive integer such that $1\le k\le n$. By induction, there are exactly $2^{n-1}$ pairs $\{\mathit{a},\mathit{b}\}$ in $E_n$ with $d(f_n(\mathit{a}),f_n(\mathit{b}))=k$. If $\{\mathit{a},\mathit{b}\}$ is one of these $2^{n-1}$ pairs, we have $$\begin{array}{rl}d(f_{n+1}(\mathit{a}|0),f_{n+1}(\mathit{b}|0))& =d(f_n(\mathit{a})|0,f_n(\mathit{b})|0)\\ & =d(f_n(\mathit{a}),f_n(\mathit{b}))\\ & =k\end{array}$$ where the second equality is because the elements in question agree in the last coordinate, so their Hamming distance is equal to the Hamming distance between the elements obtained by removing the rightmost elements. We similarly have that $$\begin{array}{rl}d(f_{n+1}(\mathit{a}|1),f_{n+1}(\mathit{b}|1))& =d(\overline{f_n(\mathit{a})}|1,\overline{f_n(\mathit{b})}|1)\\ & =d(\overline{f_n(\mathit{a})},\overline{f_n(\mathit{b})})\\ & =d(f_n(\mathit{a}),f_n(\mathit{b}))\\ & =k\end{array}$$ Therefore, there are $2\times 2^{n-1}=2^n$ pairs $\{\mathit{a},\mathit{b}\}$ from $E_{n+1}$ satisfying $d(f_{n+1}(\mathit{a}),f_{n+1}(\mathit{b}))=k$ for each $1\le k\le n$.

   Next, for any $\mathit{a}\in A_n$, we have $$\begin{array}{rl}d(f_{n+1}(\mathit{a}|0),f_{n+1}(\mathit{a}|1))& =d(f_n(\mathit{a})|0,\overline{f_n(\mathit{a})}|1)\\ & =d(f_n(\mathit{a}),\overline{f_n(\mathit{a})})+1\\ & =n+1\end{array}$$ where the second equality is because we know that the two elements being handed to $d$ have different rightmost coordinates, so their Hamming distance is one more than the Hamming distance between the elements obtained by removing the rightmost coordinates. The third equality is because $\overline{f_n(\mathit{a})}$ and $f_n(\mathit{a})$ differ in all $n$ coordinates by definition.

   There are $2^n$ elements of $A_n$, and each pair $\{\mathit{a}|0,\mathit{a}|1\}$ is in $E_{n+1}$, so we get $2^n$ pairs from $E_{n+1}$ such that $d(f_{n+1}(\mathit{a}),f_{n+1}(\mathit{b}))=n+1$. For each $k$ from $1$ through $n+1$, we have found $2^n$ pairs $\{\mathit{a},\mathit{b}\}$ from $E_{n+1}$ with the property that $d(f_{n+1}(\mathit{a}),f_{n+1}(\mathit{b}))=k$. This completes the proof.