
#1
Mar908, 06:15 PM

P: 4

Hello,
I'm working on a proof and I would like some help. I need to show that any set of 6 distinct 5bit binary numbers must have at least 5 distinct pairs of elements with Hamming distance less than or equal to 2. Hamming distance is the sum of the absolute value of each pair of coordinates: the distance between 000 and 111 is [latex]01+01+01=3[/latex] Any help would be appreciated. 



#2
Mar908, 09:41 PM

P: 39

Could you define what you mean by "pairs of elements" and 5bit binary? I don't know what either of those are.
But without even really understanding the problem my first thought is the infamous pigeionhole principal. Have you had any luck trying it? 



#3
Mar908, 10:21 PM

Sci Advisor
HW Helper
P: 3,680

Take an element A. (If it helps, you can assume without loss of generality that it's 00000.) If all other elements are within Hamming distance 1 or 2 ("close"), you're essentially done. (You'd have to show this, of course.) Otherwise, there is an element B with Hamming distance 3 or more ("far") from A to B. (If it helps, you can split this into 3 cases WLOG, where B is 00111, 01111, or 11111.) Now you can group the remaining elements into three groups: those close to both A and B, those close to A but far from B, and those close to B but far from A. If you can limit the size of one of the latter two, you're done.
On the other hand, you could try a pigeonhole approach. 



#4
Mar908, 10:39 PM

P: 813

Hamming Distance
My attempt at a counter example failed. Why not just use a computer to test all possibilities.
A: 01010 B: 11001 C: 01100 D: 00011 E: 11101 F: 00011 A,B=3 A,C=1 A,D=2 A,E=3 A,F=2 B,C=3 B,D=3 B,E=2 B,F=3 C,D=2 C,E=2 C,F=3 



#5
Mar908, 11:25 PM

P: 4

Any idea how the pigeonhole argument would work in this scenario? Thanks for the input guys. 



#6
Mar1108, 01:19 PM

P: 813





#7
Mar1108, 01:52 PM

P: 688

I have a sketch for a proof, but at this moment it is terribly informal. Here it goes.
For one given element A (without loss of generality, 00000), the count of 5bit elements with distance 0,1,2,3,4,5 to A are resp. 1,5,10,10,5,1. Thus A partitions the 5bit space in exactly half: 16 with distance > 2, and 16 (in this case, including A) with distance <= 2. Now the informal part. How would you distribute 6 elements to minimize the number of close pairs? If you choose to place the first 4 elements A,B,C,D, two at one extreme (say, A,B) and two at the other (C,D) of the 5bit range, with those 4 elements you can form 2 pairs (AB, CD), and when placing the 5th element, it will get close to either AB or CD, thus forming other 2 pairs (f.i, AE, BE). The moment you place the 6th, you will have more than 4 pairs. Alternatively, if you space equally the first 4 elements, you will have 3 pairs (AB, BC, CD); the moment you add a 5th, it will be close to other two. And you still have a 6th element to place. Terribly informal, I warned you, just a sketch. I think we need a topology guy. P.S.: I said "topology", because I think the Hamming distance is a metric on the 5bit space, thus I suspect the triangle inequality d(A,C) <= d(A,B) + d(B,C) will play a major role in a proof, possibly on the lines sketched above. 



#8
Mar1108, 09:52 PM

P: 813

I can show there is atleast 5 as follows:
It is easy to show that given any three 5 bit binary numbers there must be at least one pair with a hamming distance less then two. Now with 6 binary numbers there are 6!/(3!(63)!=20 ways to choose 3 of the 6 binary numbers. Now for any 3 of the 5 digit binary numbers there can be at most 3 other choices of 3 from the 6 numbers which share the same pair that has a hamming distance less then or equal to 2. Consequently of the 20 choices of 3 numbers which contain a pair with hamming distance less then or equal to 2 the redundancy can be no greater then 4. Consequently there must be at least 20/4=5 pairs which have a hamming distance less then or equal to 2. 



#9
Mar1208, 11:52 AM

P: 2

00000 00111 11100 ? What reasons do you have to believe that the statement is true? 



#10
Mar1208, 12:32 PM

P: 39

I tried creating a pigeonhole argument, but just wound up creating more problems. My idea was to do something like this: Let S = {A,B,C,D,E,F} be our set of 6 5bit binary numbers. There are 15 pairs of these 6 numbers. Suppose there are only 4 pairs with a Hamming Distance of 2 or 1 and find a contradiction. Given any distinct pair, they can have a Hamming Distance of 1, 2, 3, 4, or 5. We assumed there are only 4 having a Hamming Distance of 1 or 2, leaving 11 pairs with a Hamming Distance of 3, 4, or 5. Therefore, at least one of those distances must have at least 4 pairs with that distance. Clearly, there can't be 4 pairs of distance 5 since we only have 6 numbers and we'd need 8 numbers for that to happen. So can there be 4 pairs of distance 3? 4 pairs of distance 4? I have no idea... this is where I think going this route does more harm than good. On a side note, something cool I noticed while pigeonholing around is that if you select any two digits, say the 1st and 4th digit, there will be at least one pair of our numbers whose digits match there. 


Register to reply 
Related Discussions  
Hamming Code  Engineering, Comp Sci, & Technology Homework  1  
Finding the decoding transformation for a hamming code  Calculus & Beyond Homework  4  
Distance problem, Using Launcher need to find objects distance  Introductory Physics Homework  2  
Question about a hamming (7,4) code  Introductory Physics Homework  0  
Question about Hamming Codes  Linear & Abstract Algebra  0 