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

[lovePearl_maytrang]

Đặt $S=\{1,2,...,n \}$, $k$ là số nguyên dương cho trước. $T=\{(a_1,...,a_{k}) \ge S \}$.
Tìm $d$ nhỏ nhất sao cho với mọi tập con $d$ phần tử của $T$ đều tồn tại hai bộ $(a_1,...,a_{k})$ và $(b_1,...,b_k)$ sao cho $a_{i} ;b_{i}>0 (i=1,2,...,k)$.
k=2: đơn giản
k=3: bài 5 TST 2001

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

[lehoan]

Thực ra đây không phải là tập mà là các bộ có thứ tự.
Đáp số cho trường hợp k=3 là $\left\lfloor \dfrac{3n^2+1}{4} \right\rfloor +1$.
Kí hiệu $f(k;m)$ là số ngiệm nguyên dương $x_1;x_2;...;x_k$ của hệ phương trình
$D(2)=f(2;n+1)+1$
Với k=3 là $D(3)=f \left(3;n+\left\lfloor \dfrac{n}{2} \right\rfloor +2 \right)+1=f \left(3;\left\lfloor \dfrac{3(n+1)}{2} \right\rfloor \right)+1$.
Nên dự đoán là $D(k)=f \left(k;\left\lfloor \dfrac{k(n+1)}{2} \right\rfloor \right)+1$.
Với k=4 có vẻ dễ hơn cả (dĩ nhiên là phức tạp hơn với k=3) Nhưng có lẽ là sử dụng phương pháp phân hoạch tập hợp.

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

[lovePearl_maytrang]

Thực ra đây không phải là tập mà là các bộ có thứ tự.

Hic...anh nhầm
Thực ra thì để f(k,m) đạt max như em nói thì m=[k(n+1)/2] là đúng rồi (do tính chất đối xứng)
LPm đã thử với trường hợp k=4 với một số giá trị n. Kết quả ra đúng như dự đoán nhưng khá phực tạp. Bởi vì việc sắp xếp các bộ ba theo một thứ tự thích hợp là khó khăn hơn nhiều so với các bộ hai( ứng với k=3)