Problem of the Month
Problem 7: April 2023

Let $A_n$ denote the set of all $n$-tuples of $0$s and $1$s. For example, $A_2$ is the set of all ordered pairs of $0$s and $1$s or $A_2=\{(0,0),(0,1),(1,0),(1,1)\}$. To improve readability, we will omit the commas and parentheses from the elements of $A_n$. For example, the elements of $A_3$ will be denoted by $000$, $001$, $010$, $011$, $100$, $101$, $110$, and $111$.

Variables referring to elements of $A_n$ will be bold lowercase letters. For example, we might refer to elements in $A_2$ as $\mathit{a}$, or $\mathit{b}$, and so on. To refer to the coordinates of elements in $A_n$, we will use square brackets. For example, if $\mathit{a}=11010$, an element in $A_5$, then $\mathit{a}[1]=1$, $\mathit{a}[2]=1$, $\mathit{a}[3]=0$, $\mathit{a}[4]=1$, and $\mathit{a}[5]=0$.

For two elements $\mathit{a}$ and $\mathit{b}$ in $A_n$, the Hamming distance, denoted $d(\mathit{a},\mathit{b})$ between $\mathit{a}$ and $\mathit{b}$ is equal to the number of coordinates where they differ. For example, if $\mathit{a}=11010$ and $\mathit{b}=01110$, then $d(\mathit{a},\mathit{b})=2$ because $\mathit{a}[1]\ne \mathit{b}[1]$ and $\mathit{a}[3]\ne \mathit{b}[3]$, but $\mathit{a}[i]=\mathit{b}[i]$ for $i=2$, $i=4$, and $i=5$. It is important to convince yourself that $d(\mathit{a},\mathit{b})=d(\mathit{b},\mathit{a})$ for any $\mathit{a}$ and $\mathit{b}$.

The notion of a graph was defined in the extra information about the February 2023 problem, but there are also plenty of places online that have definitions. We will keep things simple here and define a graph to be a collection of vertices, some of which are connected to each other by edges. When we draw a graph, a vertex will be represented by a circle and an edge will be represented by a line segment from one vertex to another. Two examples of graphs are depicted below. The one on the left has four vertices and the one on the right has eight. Note that two edges intersecting does not necessarily imply the presence of a vertex.

For each $n$, we define a graph with $2^n$ vertices called the natural graph of $A_n$. In the natural graph of $A^n$, it is possible to label every vertex by exactly one element of $A_n$ such that there is an edge between two vertices exactly when their Hamming distance is $1$. The two examples above are the natural graphs of $A_2$ and $A_3$. They are shown again below with their vertices labelled.

A walk in a graph from vertex $v$ to vertex $w$ is a sequence of vertices starting at $v$ and ending at $w$ with the property that there is an edge connecting every pair of consecutive vertices in the sequence. The length of a walk is the number of edges it uses. For example, let $v$, $w$, $x$, and $y$ be the vertices labelled by $000$, $110$, $100$, and $010$ in the natural graph of $A_3$, respectively. Then $v,x,w$ and $v,y,w$ are walks of length $2$ from $v$ to $w$. The distance between $v$ and $w$ in a graph is equal to the shortest possible length of a walk from $v$ to $w$. In the example above, $v$ and $w$ have a distance of $2$ because there are walks of length $2$, but there are no shorter walks from $v$ to $w$.

1. Let $\mathit{a}$ and $\mathit{b}$ be elements of $A_n$. Show that $d(\mathit{a},\mathit{b})$ is equal to the distance between $\mathit{a}$ and $\mathit{b}$ in the natural graph of $A_n$.

2. For each $k$ with $1\le k\le n$, determine the number of two-element subsets $\{\mathit{a},\mathit{b}\}$ of $A_n$ that satisfy $d(\mathit{a},\mathit{b})=k$.

3. Suppose we were to relabel the vertices of the natural graph of $A_n$ by permuting the labels. That is, we keep the graph the same but use the elements of $A_n$ to label a vertex of the graph in some other way. For example, in $A_2$, we might leave $00$ and $10$ where they are and swap the positions of $01$ and $11$, as shown.

   

   When this is done, the distance in the new graph between elements of $\mathit{a}$ and $\mathit{b}$ is not necessarily equal to $d(\mathit{a},\mathit{b})$ any more. The table below has the two-element subsets of $A_2$ in the first column, $d(\mathit{a},\mathit{b})$ in the second column, and their distance in the relabelled graph in the third column.

   $\{\mathit{a},\mathit{b}\}$	$d(\mathit{a},\mathit{b})$	new distance
   $\{00,01\}$	$1$	$2$
   $\{00,10\}$	$1$	$1$
   $\{00,11\}$	$2$	$1$
   $\{01,10\}$	$2$	$1$
   $\{01,11\}$	$1$	$1$
   $\{10,11\}$	$1$	$2$

   Among the four subsets $\{\mathit{a},\mathit{b}\}$ with $d(\mathit{a},\mathit{b})=1$, there are two that have a distance in the relabelled graph of $1$ and two that have a distance in the relabelled graph of $2$.

   Now for the question: For each $n$, find a way to permute the elements of $A_n$ so that the following happens: Among all two-element subsets $\{\mathit{a},\mathit{b}\}$ of $A_n$ with $d(\mathit{a},\mathit{b})=1$, there are the same number with each possible distance in the relabelled graph.