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

[Explorer]

Cho tập S gồm các xâu nhị phân có độ dài n sao cho với mọi X,Y thuộc S thì X,Y khác nhau ở ít nhất 3 vị trí. CMR:$|S|\leq \frac{2^{n}}{n+1}$

[Hoang72]

Gọi $\mathcal{F}$ là tập tất cả các xâu nhị phân có độ dài $n$.

Định nghĩa hai xâu phân biệt được gọi là "tách rời" là hai xâu khác nhau ở ít nhất $3$ vị trí.

Lấy $S$ là tập con có nhiều phần tử nhất có thể của $\mathcal{F}$ thoả mãn trong hai phần tử bất kì của $S$ thì "tách rời". 

Thế thì ta đếm số cặp xâu $(A,B)$ sao cho $A\in S, B\in \mathcal{F}\setminus S$ và $A,B$ khác nhau ở không quá $1$ vị trí.

$\bullet$ Đếm theo $A$: Nhận thấy với mỗi xâu $A\in S$, ta chỉ việc thay đổi $1$ trong $n$ vị trí để được xâu khác $A$ không quá $1$ vị trí. Do đó số bộ ít nhất là $nk$.

$\bullet$ Đếm theo $B$: Với mỗi $B\in \mathcal{F}\setminus S$, ta tìm được không quá $1$ xâu thuộc $S$ mà khác $B$ không quá $1$ vị trí. Thật vậy, giả sử có hai xâu như vậy là $A_1,A_2$. Thế thì $A_1,A_2$ phải khác nhau không quá $2$ vị trí, mâu thuẫn.

Như vậy suy ra $nk \leq 2^n - k$, hay $k\leq \frac{2^n}{n+1}$. Ta có đpcm.