Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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 1

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\}$.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.