Hamming Distance problem

[Chironic]

Hi,

I've been set an assignment to find the maximum hamming distance between 2 nodes for level i. I'm having some trouble mainly because I don't understand what a level is. Could anyone help me out?

[Yakk]

You might want to actually copy the question.

[Yakk]

Ok, nevermind, I managed to read your mind.

The question is actually "find the maximum hamming distance between two vertices at level i of an n-cube, where the level of a vertex in an n-cube is the number of 1s in the coordinate description of the cube, where the vertices are elements of {0,1}^n, connected in the obvious way."

Mentioning the n-cube would have made reading your mind easier.

[Chironic]

Sorry, yes it's for an n-cube. I just don't understand the "level" part

[Xanthir]

Huh, that seems pretty trivial.

For a 2-cube, you've got the four vertices (0,0), (0,1), (1,0), and (1,1). According to the definition in Yakk's post, the levels are respectively 0, 1, 1, and 2, because that's the number of 1s in each vertex.

[Yakk]

For a 2-cube, you've got the four vertices (0,0), (0,1), (1,0), and (1,1). According to the definition in Yakk's post, the levels are respectively 0, 1, 1, and 2, because that's the number of 1s in each vertex.

Yep.

Huh, that seems pretty trivial.

Yep.

Sorry, yes it's for an n-cube. I just don't understand the "level" part

What part of the description I just posted of what level means wasn't clear?

Do you understand what "{0,1}^n as coordinates of the vertices of an n-cube" means?

Do you understand what Rⁿ means? Same thing, but where the elements of the vector are 0 or 1, and not all of R.

Do you understand "The level of the vertex is the number of 1s"?

[Meem1029]

So basically it's the number of 1s in A XOR B?

[Cleverbeans]

So basically it's the number of 1s in A XOR B?

Yes. The treatment I'm familiar with defines strings to be elements of C^n where n is max string length and C is the field of integers modulo 2. From here the norm |.| is defined to be the number of 1s in the string, and the metric is naturally given as d(x,y) = |x-y| which is the how we extend the Euclidian norm to the usual distance function. Another way to think of it is as the number of places in which the two strings differ, so say d(0010,1010) = 1 and d(1111,1010) = 2 just by inspection on where the are not the same. Simple enough to calculate with.