Chủ đề này có 4 trả lời

[QUANVU]

Chứng minh rằng không thể có nhiều hơn 4096 dãy nhị phân độ dài 24 sao cho hai dãy bất kì trong đó có ít nhất tám vị trí khác nhau.

Brasil 2002

Bài viết đã được chỉnh sửa nội dung bởi dark templar: 16-03-2013 - 18:08

[hoang]

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

[QUANVU]

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.

Đoạn này dùng bđt tam giác là xong!

Ổn lắm, ừ nhưng mà đoạn cuối dùng luật bù trừ à?

[hoang]

Cach giai nay co ve sai roi do bdt o cuoi cung khong dung, ai co the kiem tra ho xem BDT so o cuoi loi giai co dung khong vay

[QUANVU]

Ờ ,nếu đoạn cuối mà sai thì tiếc thật!Mình không để ý đoạn cuối này ,tưởng bạn tính toán cụ thể rồi cơ

Bây giờ bác cố nốt chặng cuối này nhé bác hoang.