CEMC Banner

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 \(\boldsymbol{a}\), or \(\boldsymbol{b}\), and so on. To refer to the coordinates of elements in \(A_n\), we will use square brackets. For example, if \(\boldsymbol{a}=11010\), an element in \(A_5\), then \(\boldsymbol{a}[1]=1\), \(\boldsymbol{a}[2]=1\), \(\boldsymbol{a}[3]=0\), \(\boldsymbol{a}[4]=1\), and \(\boldsymbol{a}[5]=0\).

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

Four vertices connected by four edges forming a square. Four vertices connected by four edges form a first square, and another four vertices connected by four edges form a second square. The second square is slightly offset from the first so the squares overlap in a smaller square area. Corresponding pairs of vertices of the two squares are connected by four additional edges.

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.

Starting at the bottom left corner and moving clockwise around the perimeter of the square, the vertices are labelled 0 0 then 0 1 then 1 1 then 1 0. In the first square, starting at the bottom left corner and moving clockwise around the perimeter, the vertices are labelled 0 0 0 then 0 0 1 then 1 0 1 then 1 0 0. In the second square, starting again at the bottom left corner and moving clockwise around the perimeter, the vertices are labelled 0 1 0 then 0 1 1 then 1 1 1 then 1 1 0.

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 \(\boldsymbol{a}\) and \(\boldsymbol{b}\) be elements of \(A_n\). Show that \(d(\boldsymbol{a},\boldsymbol{b})\) is equal to the distance between \(\boldsymbol{a}\) and \(\boldsymbol{b}\) in the natural graph of \(A_n\).

  2. For each \(k\) with \(1\leq k \leq n\), determine the number of two-element subsets \(\{\boldsymbol{a},\boldsymbol{b}\}\) of \(A_n\) that satisfy \(d(\boldsymbol{a},\boldsymbol{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.

    First graph: Starting at the bottom left and moving clockwise, the vertices are labelled 0 0 then 0 1 then 1 1 then 1 0. Second graph: Starting at the bottom left and moving clockwise, the vertices are labelled 0 0 then 1 1 then 0 1 then 1 0.

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

    \(\{\boldsymbol{a},\boldsymbol{b}\}\) \(d(\boldsymbol{a},\boldsymbol{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 \(\{\boldsymbol{a},\boldsymbol{b}\}\) with \(d(\boldsymbol{a},\boldsymbol{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 \(\{\boldsymbol{a},\boldsymbol{b}\}\) of \(A_n\) with \(d(\boldsymbol{a},\boldsymbol{b})=1\), there are the same number with each possible distance in the relabelled graph.