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

[lehoan]

bài toán mở đầu:
Kí hiệu $S_n=\{1;2;...;n\}$.
Hãy tìm số nguyên dương $k$ nhỏ nhất để với mọi tập con có $k$ phần tử của $S_{n}$ thì có hai phần tử là bội của nhau.
Bài toán mở rộng hơn 1 chút.
Tim số nguyên dương $k$ nhỏ nhất để với mọi tập con cớ $k$ phần tử của $S_{2^m.n}$ thì có $m+1$ phần tử $x_0;x_1;...;x_m$ mà $x_i|x_{i+1} \forall i=0;1;...;m$.

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

[chuyentoan]

k=[(n+1)/2]

[lehoan]

lehoan cho đáp số nhé đó là http://dientuvietnam....cgi?k=2^mn-n 1

[Hr MiSu]

Ta thấy :$\left \lfloor \frac{n+1}{2} \right \rfloor$, $\left \lfloor \frac{n+1}{2} \right \rfloor$ +1,..., n  đôi một nguyên tố cùng nhau, do đó k> $\left \lfloor \frac{n+1}{2} \right \rfloor$ . ta chứng minh k=$\left \lfloor \frac{n+1}{2} \right \rfloor$+1. 

Thật vậy, xét tập con có k phần tử của S(n), nếu chứa phần tử 1 thì luôn thỏa mãn

ta xét các tập ko chứa 1, nếu nó chứa 2 thì cũng luôn thỏa mãn, cứ như thế, ta suy ra tất cả các tập con đều thỏa mãn

Bài viết đã được chỉnh sửa nội dung bởi Hr MiSu: 12-07-2018 - 02:05