# Comp Sci Math; Hamming Distance

I've been tasked with this question but I have no idea how to answer it.

What is the maximum possible hamming distance between two points from level i in a n-cube?

-
What's a level in an n-cube? – Aleš Bizjak Sep 28 '11 at 19:48
Its written as a "node", I don't quite understand the question – David Sep 28 '11 at 19:58
"node from level i" – David Sep 28 '11 at 20:00

## 1 Answer

The only definition of level that I’ve seen in this context is the following one, which I’ll assume for this answer:

Level $i$ of the $n$-cube is the set of vertices that have $i$ coordinates equal to $1$ and $n-i$ coordinates equal to $0$.

If $i\le n/2$, you can change all $i$ of the $1$’s to $0$’s and $i$ of the $0$’s to $1$’s to get two nodes in level $i$ at Hamming distance $2i$, and it’s pretty clear that you can’t do better than this. If $i>n/2$, any two sets of $i$ coordinates must have an overlap of at least $2i-n$ places. The node $(1,1,\dots,1,0,\dots,0)$ with $i$ $1$’s followed by $n-i$ $0$’s and its reversal are then members of level $i$ at Hamming distance whose middle $2i-n$ coordinates are identical, so the Hamming distance between these nodes is $n-(2i-n) = 2n-2i$; again it’s pretty clear that this is the best you can do. (In this case you’re changing all $n-i$ of the $0$’s of each node to $1$’s and $n-i$ of the $1$’s to $0$’s.)

The two results can be combined: the maximum Hamming distance between two nodes on level $i$ is $2 \min\{i,n-i\}$.

-
An equivalent definition of a node at level $i$ is that one traverses $i$ edges (climbs $i$ levels) of the $n$-dimensional hypercube with vertices $\{0,1\}^n$ in moving from the origin $(0,0,\ldots, 0)$ to a node at level $i$. – Dilip Sarwate Sep 28 '11 at 22:59