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

[Sangnguyen3]

Cho tập $X=\{1;2;3;\ldots ;3000\}$. Có tồn tại hay không 1 tập $A$ có 2000 phần tử và với mỗi $x\in A \Rightarrow 2x\notin A$ ?

Bài viết đã được chỉnh sửa nội dung bởi perfectstrong: 27-09-2023 - 14:12
Tiêu đề & LaTeX

[nhungvienkimcuong]

Phân hoạch tập hợp $X$ thành các tập con $X_{2i-1}$ như sau

$$X_{2i-1}=\Big\{2^j(2i-1)\mid j\in\mathbb{N},\ 2^j(2i-1)\le 3000\Big\},\quad i\in\{1,2,\dots,1500\}.$$

Từ đây ta thấy rằng để tập $A$ thỏa đề có số phần tử lớn nhất thì ở mỗi tập hợp $X_{2i-1}$ ta chọn $\left \lfloor \frac{|X_{2i-1}|+1}{2} \right \rfloor$ phần tử (không đồng thời chọn cả $x$ lẫn $2x$). Như vậy số phần tử lớn nhất của $A$ là

$$\sum_{i=1}^{1500}\left \lfloor \frac{|X_{2i-1}|+1}{2} \right \rfloor=\sum_{i=1}^{1500}\left \lfloor \frac{1}{2}\left \lfloor \log_2\left ( \frac{3000}{2i-1} \right )+1 \right \rfloor+\frac{1}{2} \right \rfloor.$$

[poset]

Phân hoạch tập hợp $X$ thành các tập con $X_{2i-1}$ như sau

$$X_{2i-1}=\Big\{2^j(2i-1)\mid j\in\mathbb{N},\ 2^j(2i-1)\le 3000\Big\},\quad i\in\{1,2,\dots,1500\}.$$

Từ đây ta thấy rằng để tập $A$ thỏa đề có số phần tử lớn nhất thì ở mỗi tập hợp $X_{2i-1}$ ta chọn $\left \lfloor \frac{|X_{2i-1}|+1}{2} \right \rfloor$ phần tử (không đồng thời chọn cả $x$ lẫn $2x$). Như vậy số phần tử lớn nhất của $A$ là

$$\sum_{i=1}^{1500}\left \lfloor \frac{|X_{2i-1}|+1}{2} \right \rfloor=\sum_{i=1}^{1500}\left \lfloor \frac{1}{2}\left \lfloor \log_2\left ( \frac{3000}{2i-1} \right )+1 \right \rfloor+\frac{1}{2} \right \rfloor.$$

Một cách để chọn tập $A$ như vậy là lấy tất cả các phần tử có dạng $(2i-1)4^k$. Có thể kiểm tra được rằng tập $A$ thỏa mãn $x\in A\Rightarrow 2x\notin A$ và với cách chọn như vậy số phần tử của $A$ trong mỗi tập hợp $X_{2i-1}$ là lớn nhất ($\left\lfloor\frac{|X_{2i-1}|+1}{2}\right\rfloor$ phần tử) nên $|A|$ cũng lớn nhất. 
Với $k=0$ thì $2i-1\leq 3000\Rightarrow i\leq 1500$ nên có $1500$ cách chọn $i$.
Với $k=1$ thì $4(2i-1)\leq 3000\Rightarrow 2i-1\leq 750\Rightarrow i\leq 375$ nên có $375$ cách chọn $i$.
Với $k=2$ thì $16(2i-1)\leq 3000\Rightarrow 2i-1\leq 187\Rightarrow i\leq 94$ nên có $94$ cách chọn $i$.
...
Cứ như vậy tính được $|A|=1500+375+94+23+6+1=1999<2000$ (gần được), mà ta đã chọn $A$ sao cho $|A|$ lớn nhất nên không tồn tại tập $A$ với $|A|=2000$ như đề bài.
Câu hỏi nhỏ là với $n$ nào thì với tập $X=\{1,2,...,3n\}$ có chứa tập $|A|=2n$ sao cho $x\in A\Rightarrow 2x\notin A$? 

Bài viết đã được chỉnh sửa nội dung bởi poset: 29-09-2023 - 22:23