Khoảng cách Hamming

KHOẢNG CÁCH HAMMING 
I. Định nghĩa 
Khoảng cách Hamming giữa hai xâu (string) có độ dài bằng nhau là số vị trí khác 
nhau ở các kí tự tương ứng. 
Ví dụ: abcdefg và abemnfk có khoảng cách Hamming là 4; 1100010 và 0101110 có 
khoảng cách Hamming là 3. 
II. Các kết quả liên quan đến khoảng cách Hamming. 
Cho và tập hợp có phần tử. Gọi là tập hợp chứa các xâu (mỗi 
kí tự là một phần tử của X hoặc phần tử 0) có độ dài bằng và khoảng cách 
Hamming có độ dài không nhỏ hơn . Kí hiệu ( ) là số phần tử lớn nhất 
của tập hợp . Khi đó 
i) Nếu chẵn và thì 
 ( ) [
] 
ii) Nếu lẻ và thì 
 ( ) [
] 
iii) Nếu chẵn thì 
 ( ) 
iv) Nếu lẻ thì 
 ( ) 
 Chứng minh. Giả sử * +. Ta đồng nhất mỗi phần tử của C 
với một xâu nhị phân dạng , trong đó nếu ở vị trí thứ của xâu là và 
 nếu vị trí thứ của xâu là . 
i) Ta sẽ đánh giá 
∑ ( )
theo 2 cách khác nhau, ở đây kí hiệu ( ) là khoảng cách Hamming giữa hai 
xâu . 
+) Số cách chọn bộ có thứ tự ( ) là ( ) suy ra: 
∑ ( )
 ( ) 
+) Xét ma trận , trong đó mỗi dòng là một phần tử của . Gọi là số số 0 
ở cột thứ và tương ứng ở cột thứ đó có số 1. Do xét quan hệ hai xâu 
 , có tính đối xứng nên suy 
∑ ( )
 ∑ ( )
Do đó từ hai cách đánh giá ở trên ta được: 
∑
 ∑ ( )
 ( ) 
Hay ( ) 
. Kết hợp với giả thiết suy ra đpcm. 
ii) Lặp lại cách chứng minh tương tự như trên nhưng đối với tập * + 
III. Bài tập áp dụng 
Bài 1 (Vĩnh Phúc 2012, vòng 2) Có 7 em học sinh được lập thành nhóm hoạt động 
ngoại khóa, mỗi học sinh có thể tham gia nhiều nhóm hoạt động. Biết rằng với hai nhóm 
tùy ý thì có ít nhất 4 học sinh chỉ tham gia vào một trong hai nhóm đó. 
 Tìm giá trị lớn nhất có thể của . 
Lời giải 
Cách 1 (Đáp án chính thức) 
Ta lập các “bộ ba”, mỗi bộ ba gồm hai nhóm nào đó cùng với một học sinh không tham 
gia vào một trong hai nhóm đó. Giả sử có bộ ba như vậy. Theo bài ra ta có bất đẳng 
thức sau: 
 ( ) 
Nếu học sinh nào đó tham gia nhóm, thì sẽ không tham gia nhóm. Như 
vậy, học sinh đó sẽ tham gia vào đúng ( ) bộ ba. Từ đó ta có: 
 ∑ ( )
 ( ) 
Mặt khác 
 ( ) 
Suy ra 
 ( ) 
Tức là . 
Ví dụ sau đây cho một cách phân nhóm với , các học sinh là : 
 ( ) ( ) ( ) ( ) ( ) 
 ( ) ( ) ( ) 
Cách 2 (Sử dụng kết quả liên quan đến khoảng cách Hamming) 
Giả sử 7 học sinh là và đặt * +. Ta coi mỗi nhóm là một 
xâu dạng , trong đó nếu nhóm đó chứa , nếu nhóm đó không 
chứa . Khi đó theo giả thiết khoảng cách Hamming không nhỏ hơn . Áp dụng kết 
quả phần 2.i ở trên với ta được và trong đánh giá dễ dàng chỉ ra 
được dấu bằng. 
Bài 3. Cho 1 2, ,..., kA A A là các tập con của tập  1,2,...,10S  sao cho: 
a) 5, 1,2,..., ;iA i k  
b) 2,1 .i jA A i j k    
Tìm giá trị lớn nhất có thể có của k . 
Lời giải. Ta coi mỗi tập con tA là một xâu nhị phân có dạng 1 2 10...t t t trong đó 1it  nếu tA 
chứa i và 0it  nếu tA không chứa i . Do 2,1 .i jA A i j k    nên khoảng cách 
Hamming giữa hai tập ,1 .i jA A i j k   không nhỏ hơn 6. Do đó theo kết quả của định 
lí phần (i) ta được: 
6
2 6
2.6 10
k
 
   
. 
Bài 3. Cho tập hợp * +. Hai tập con và của được gọi là không 
giống nhau nếu | | , trong đó ( ) ( ). Cho tập hợp 
* + mà mỗi phần tử là một tập con của gồm phần tử đôi một không 
giống nhau. 
a) Chứng minh rằng 
b) Chứng minh rằng 
 ( )
. 
Lời giải. Ta sẽ chứng minh phần b vì phần a là hệ quả của nó. 
Ta coi mỗi tập là một xâu dạng , trong đó trong đó nếu 
chứa , nếu không chứa . Khi đó theo giả thiết khoảng cách Hamming không 
nhỏ hơn . Áp dụng kết quả phần 2.ii ở trên với ( ) ta được 
 [
 ( ) 
] [
] 
 ( )
 và trong đánh giá dễ dàng chỉ ra được dấu 
bằng. 
Bài 4. Trong một cuộc thi có n thí sinh và p giám khảo, ở đó ,n p là các số nguyên dương 
, 2p  . Mỗi giám khảo đánh giá từng thí sinh và cho kết luận thí sinh đó đỗ hay trượt. 
Giả sử k là số thỏa mãn điều kiện: Với hai giám khảo bất kì, số thí sinh mà họ cho kết 
quả giống nhau nhiều nhất là k. Chứng minh rằng 
 
2
2 1
k p
n p



. 
Lời giải. Giả sử n thí sinh là 1 2, ,..., ns s s . Mỗi giám khảo cho tương ứng với một xâu 
1 2... nt t t , trong đó 1it  nếu thí sinh đỗ, và 0it  nếu thí sinh trượt. Theo giả thiết thì 
khoảng cách Hamming giữa hai giám khảo bất kì sẽ không nhỏ hơn n k . Ta xét hai 
trường hợp sau: 
TH1. Nếu  
 
1 2
2
2 2 1
k p
n k n
n p

   

TH2. Nếu  2 n k n  thì ta xét 2 khả năng sau: 
+) Nếu n k chẵn thì theo kết quả của định lí ta được: 
   
 
 
2
2 2 2 2 2
2 2 2 1
n k n k k p
p p n k n k
n k n n k n n p
   
       
     
+) Nếu n k lẻ thì theo kết quả của định lí ta được: 
   
 
   
1 1
2 2 2 1 2 2 2
2 1 2 1
2 1 2
.
2 1 2 1
n k n k
p p n k n k
n k n n k n
k p n p
n p n p
    
        
      
  
  
 
Vậy ta luôn có đánh giá 
 
2
2 1
k p
n p



. 
Bài 5. Cho 1 2, ,..., mA A A là các tập hợp con của tập hợp  1,2,...,2013S  ,
505, 1,2,...,iA i m  và 1,1i jS S i j m    . Chứng minh rằng 672.m 
Lời giải. Ta coi mỗi tập con tA là một xâu dạng 1 2 2013...t t t , trong đó 1it  nếu tA chứa 
phần tử i và 0it  nếu tA không chứa phần tử i. Do 1,1i jS S i j m    nên hai tập bất 
kì sẽ có khoảng cách Hamming không nhỏ hơn 2.504 1008 . Theo kết quả định lí trên ta 
được: 
1008
2 672.
2.1008 2013
m
 
   
Như vậy với mỗi cách tạo ra khoảng cách Hamming của hai đối tương nào đó ta 
được một dạng bài tập tương đối khó. Trong tất cả các dạng bài tập liên quan đến khoảng 
cách Hamming thì ví dụ 2 thật tinh tế và sâu sắc.