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

[leecom]

Mời các bạn giải quyết bài toán:
Cho $a=(a_{1}, a_{2},...,a_{ n})$ là một dãy số nguyên dương gồm các số hạng phân biệt. Gọi $m$ là số các bộ $(a_{i},a_{j},a_{k})$ sao cho $(a_{i},a_{j},a_{k})$ là các số nguyên liên tiếp thỏa mãn: $a_{j}=a_{i}+1$ và $a_{k}=a_{j}+1$ và $1\le i<j<k\le n$. Tìm $max$ $n$

Bài viết đã được chỉnh sửa nội dung bởi leecom: 07-01-2007 - 21:32

[manutd]

bộ ba số nguyên liên tiếp có cần sắp thứ tự từ bé đến lớn không?

[vnm]

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

[leecom]

Xin lỗi, mình đã chỉnh sửa lại đề rồi.
Bài vnm giải là bài toán thứ 2 mà mình muốn nói đến. Đó là trường hợp $a=(a_{1},a_{2},...,a_{ n})$ là một dãy số mà các số hạng không nhất thiết phân biệt.
Tuy nhiên bài toán 1 giải rất dễ.

Còn nếu 3 số đó liên tiếp không cần thứ tự thì bài toán sẽ trở nên rất rất khó, bởi vì bài 2 đã là IMO SHORLIST rồi.

Bài viết đã được chỉnh sửa nội dung bởi leecom: 07-01-2007 - 21:39