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

[1001001]

Cho mn+1 số thực phân biệt. C/m tồn tại 1 dãy tăng với ít nhất n+1 phần tử hoặc 1 dãy giảm với ít nhất m+1 phần tử.

[tanlsth]

Gọi $ A_1 $ là tập chứa các phần tử đầu tiên và các phần tử giảm theo thứ tự từ nó
$ A_{i+1} $ là dãy chứa phần tử đầu tiên $ \no \in A_1,..,A_i $ và các phần tử giảm dần từ nó
Giả sử có $ k $ tập như vậy
Suy ra $ |A_1|+..+|A_k|=mn+1 $
Nếu $k \leq n $tồn tại $ |A_i| \geq m+1 $ thì ta có điều phải chứng minh
Nếu $ k \geq n+1 $ thì chọn phần tử bất kì $ a_k \in A_k $
Giả sử đã chọn được $ a_k>a_{k-1}>..>a_{i+1} ,a_j \in A_j $ theo thứ tự của dãy thì luôn tồn tại $ a_i \in A_i $ đứng trước $ a_{i+1}$ thỏa mãn $ a_i<a_{i+1} $(vì nếu không thì ta có thể bổ sung $ a_{i+1}$ vào dãy $ A_i $)
Khi đó ta có dãy $ a_1<..<a_k $ đúng theo thứ tự của dãy thỏa mãn bài toán

Bài viết đã được chỉnh sửa nội dung bởi tanlsth: 10-01-2007 - 11:24

[1001001]

Hôm qua có người bạn hỏi lại bài này, mình nhớ lại cách làm của tanlsth thì thấy có chỗ hổng vì chắc gì a[1],a[2]...a[k] đảm bảo về mặt thứ tự của dãy con.
Sau đây là lời giải đúng:
Với mỗi i [1,mn+1] Z gọi t[i] là độ dài lớn nhất của dãy đơn điệu giảm bắt đầu từ a[i].
Nếu tồn tại t[i]>m+1 => đpcm.
Nếu không phải tồn tại n+1 số t[x[1]]=t[x[2]]=...=t[x[n+1]]=s (s [1,m] Z)(x[i]<x[i+1]) .
Ta c/m a[x[i]]<a[x[i+1]]. Thật vậy nếu không ta có thể bổ sung a[x[i]] vào dãy giảm bắt đầu từ a[x[i+1]] thì được t[x[i]]:geqs+1 (mâu thuẫn). Vậy n+1 số a[x[i]] (i [1,n+1] Z) tạo thành 1 dãy đơn điệu giảm.

Bài viết đã được chỉnh sửa nội dung bởi 1001001: 20-12-2006 - 07:59

[leecom]

Gọi là tập chứa phần tử đầu tiên và tất cả các phần tử giảm dần từ số đó
Gọi là tập chứa phần tử đầu tiên và các phân tử giảm dần từ số đó
Giả sử có tập như vậy
suy ra
Nếu suy ra tồn tại
suy ra điều phải cm
Nếu thì gọi
suy ra
Chọn dãy ta có điều phải cm

Cách làm của Tân đúng rồi!

[1001001]

Ví dụ : 9=4.2 +1 (m=4, n=2).
Xét dãy: 9, 15, 14, 13, 18, 17, 7, 4, 16.
A[1]=9, 7, 4
A[2]=15, 14, 13.
A[3]=18, 17, 16.
k=3 > n=2.
a[1]=min(A[1])=4.
a[2]=min(A[2])=13.
a[3]=min(A[3])=16.
4, 13, 16 không phải là 1 dãy con của dãy đã cho.

[tanlsth]

Anh đã sửa lại rồi đó