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

[QUANVU]

Tìm $S$ là tập con của $\{1,2,...,n\}$ sao cho $S$ có thể có nhiều nhất bao nhiêu phần tử?

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

[lovePearl_maytrang]

Để đơn giản chỉ cần xét với $n=4m$. Giả sử $d(x_{i})$ đôi một khác nhau và $d(x_{i}) \in \{1,3,5,...,4m-1 \}$
Đặt $A=\{1,3,...,2m-1 \};B=\{2m+1,2m+3,...,4m-1 \}$.
Nếu $y \in B$ mà $\exists i$ để $y=d(x_{i})$ thì dễ thấy không tồn tại $i$ để $d(x_{i})=d(y-1) \in A$. Ngoài ra với các $y \in B$ thì $d(y-1)$ là đôi một khác nhau. Do đó có không quá $m$ giá trị của $d(x_{i});k ;m$
Có thể lấy $S=\{2m,2m+2,...,4m-2 \}$ để kiểm chứng.

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

[lehoan]

Đáp số là $\left\lfloor \frac{n+2}{4} \right\rfloor$
Thêm 1 bài nữa
Hãy tìm số $k$ lớn nhất sao cho tồn tại $k$ số thuộc $\{1;2;..;n\}$ và một số bất kì trong $k $ số đó không là ước của $k-1$ số còn lại.

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

[nhatquangsin]

Hãy tìm số $k$ lớn nhất sao cho tồn tại $k$ số thuộc $\{1;2;..;n\}$ và một số bất kì trong $k $ số đó không là ước của $k-1$ số còn lại.

Trước hết ta xét bài toán đảo:

Tìm số $k$ nhỏ nhất sao cho tồn tại $k$ số thuộc tập hợp $X=\{1;2;...;n\}$ sao cho trong $k$ số đó tồn tại hai số $a$ và $b$ sao cho $a\vdots b$.

Ta giải bài toán phụ như sau:

Xét tập $S=\left \{ a_{1};a_{2};...;a_{k} \right \}\subseteq X$. Biểu diễn $a_{i}=2^{\alpha _{i}}.b_{i},(i=\overline{1,k})$ và $b_{i}$ là những số lẻ.

Vì trong $X$ có $\left \lfloor \frac{n+1}{2} \right \rfloor$ số lẻ nên suy ra $k>\left \lfloor \frac{n+1}{2} \right \rfloor$(theo nguyên lý Dirichlet).

 

Trở lại bài toán ta có $k\leq \left \lfloor \frac{n+1}{2} \right \rfloor$.

Vậy $max_{k}=\left \lfloor \frac{n+1}{2} \right \rfloor$

Bài viết đã được chỉnh sửa nội dung bởi nhatquangsin: 20-08-2013 - 15:38