ta giải bài toán với điều kiên bộ ba liên tiếp sắp xếp từ lớn đến bé
Dễ thấy có thể giả sử $a_1\leq\ a_2\leq\...a_n$ vì nếu a_i>a_{i+1} ta đổi chỗ 2 phần tử này vầ nhận được 1 dãy có số bộ tốt không nhỏ hơn dãy ban đầu
nếu tồn tại $a_{i+1}>a_i+1$ ta xét dãy mới như sau $a'_{k}=a_{k}-1$ với mọi $k\geq\i$;
ta chứng minh được dãy mới có số bộ tốt không nhỏ hơn dãy ban đầu
Vì vậy ta có thể giả sử $a_1=..a_{t_1}<a_{t_1+1}=...a_{t_1+t_2}<..a_{t_k}=a_n$ $a_{t_{i+1}}=a_{t_i}+1$;$t_1+t_2+...t_k=n$
Số bộ tốt là $t_1t_2t_3+t_2t_3t_4+...$
ta thấy không thể có $k\geq\ 4$ vì nếu xét dãy mới (t_2;t_3;t_1+t_4...t_k) sẽ có số bộ tốt lớn hơn dãy ban đầu
vậy số bộ tốt lớn nhất là max $abc;a+b+c=n$
nếu n=3k thì max=k^3
n=3k+1 max=k^2(k+1)
n=3k+2 max=k(k+1)^2
Bài viết đã được chỉnh sửa nội dung bởi vnm: 07-01-2007 - 14:03
The day you were born, you cried but the others were smiling; Live your life in a way that one day you die with a smile and all the others cry