Gia su ton tai 4096 day nhi phan nhu vay.
Xet khoang cach Hamming cho boi d(a,b)=|a1-b1|+....+|a24-b24|
Ta co khoang cach giua 2 day bat ki khong it hon 8 . Voi moi day nhi phan a=(a1,..,a24) ta xet tap S(a) cac day co khoang cach den no khong vuot qua 4( hinh cau ban kinh 4).
Xet 2 tap hop bat ki S(a), S(b) ung voi 2 day trong so 4096 day da cho a=(a1,..,a24) va b=(b1,..,b24).
Gia su rang x=(x1,..,x24)
S(a)
S(b)
Khi do so vi tri cua a sai khac so voi b nhieu nhat la 4, so vi tri cua b sai khac voi x nhieu nhat la 4 . Nhu vay so vi tri sai khac cua a va b khong vuot qua 8. Theo gia thiet thi ta phai co so cac vi tri khac nhau trong 2 chuoi nhi phan a va b dung bang 8.
Nhu vay ta phai co x khac a o cac vi tri (i1,i2,i3,i4) va x khac b o 4 vi tri (i5,i6,i7,i8). Cac chi so nay can phai doi mot khac nhau. Nhan xet rang o cac vi tri nay thi gia tri cua a va b khac nhau nen so luong cac day x nam trong ca S(a) va S(b) khong the vuot qua so cach chon 4 chi so (i1,i2,i3,i4) trong so 8 vi tri khac nhau cua a va b .
Ta co Card( S(a)
S(b)) hoac bang 0 hoac khong vuot qua C(4,8)
Voi moi a ta co
Card(S(a))= s=C(0.24) +C(1,24) +C(2,24) +...+ C(4,24) ( khong biet cach danh
cong thuc to hop)
Nhan thay rang hop cua 4096 tap hop nay co luc luong khong it hon
4096. s -C(4,8). 4096(4096-1)/2 > 4096.4096 = 2^24 = so cac day nhi phan do
dai 24 ( mau thuan )
Bài viết đã được chỉnh sửa nội dung bởi hoang: 20-07-2005 - 22:29