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

[nhungvienkimcuong]

Gọi $\mathcal{S}$ là tập hợp có tính chất $:$

$\text{i})$ Gồm các xâu nhị phân có độ dài $15$.

$\text{ii})$ Hai phần tử phân biệt của $\mathcal{S}$ là hai dãy khác nhau tại ít nhất $3$ vị trí.

Chứng minh rằng $\left | \mathcal{S} \right |\le 2^{11}$

 

[ThEdArKlOrD]

Suppose there are $t$ elements in $S$

For each element $p\in S$, we write down $p$ in a line, under word $p$, we write down all word different from $p$ by exactly $1$ letter, note that there are total $15+1$ words from each $p$ (including $p$)

Note that among any two words differ at least $1$ letter

So $(15+1)\times t \leq 2^{15}$ give us $t\leq 2^{11}$

Bài viết đã được chỉnh sửa nội dung bởi ThEdArKlOrD: 17-04-2016 - 22:26