Toán cấp 3 khó quá :(

Toán cấp 3 khó quá

Ai giúp với
tập N các số tự nhiên = {0,1,...}

1) Cho n tự nhiên, n>=2
Hỏi có bao nhiêu hoán vị (a1,...,an) của (1,...,n) thoả mãn:
mọi 2<= i <= n hoặc ai > max {a1,...,ai-1} hoặc ai < min {a1,...,ai-1}

2) n,k tự nhiên, k<= n
fk = số hoán vị (a1,...,an) của (1,...,n) thoả mãn có đúng k số i mà ai = i
a) (Canada 83) Chứng minh |f0 - f1| = 1
b) (IMO 87) CM: tổng k*fk = n! ( k=0,...,n)





Shinichi Kudo

3) Cho S là 1 tập n phần tử. A1,...,An là n tập con khác nhau của tập S. CMR: tồn tại x thuộc S sao cho A1-{x},...,An-{x} là khác nhau.
4) Cho 2n+1 số biết rằng khi bỏ đi 1 số bất kỳ thì ta có thể chia 2n số còn lại thành 2 phần có tổng bằng nhau và bằng số phần tử. Cmr: tất cả các số này đều bằng nhau
Các bác giải giúp em với, nhất là bài 3 í

Shinichi Kudo

Tiếp tục,
5)Trong 2n số tự nhiên liên tiếp, chọn n+1 số bất kỳ. CMR: có 2 số nguyên tố cùng nhau, 2 số chia hết cho nhau (Bài toán Erdös )
6) A là 1 tập hợp các từ có độ dài n chữ, mỗi chữ là 0 hoặc 1, 2 từ khác nhau thuộc A có ít nhất 3 vị trí khác nhau.
CMR: |A| <= 2^n/(n+1)

Shinichi Kudo

Bác này câu bài quá. Post 1 bài là đủ còn post đến những 3 bài.
Xem qua một lượt thấy bác cần nhất bài 3 thì nói qua 1 chút. Bài này của bọn Ấn Độ hay sao ấy. Chứng minh nó dùng quy nạp ấy mà. Bác tự suy nghĩ tiếp nhé.
Bài 5 hình như chứng inh cho trưòng hợp n nguyên tố trước. Sau đó mới chứng minh n bất kỳ. Lâu rồi không làm toán nên không nhớ rõ lắm. Thông cảm nhé. Nhất là mới chỉ nhìn sơ qua

Life is ocean of misery!
Đã là phúc thì không phải là hoạ, đã là hoạ thì không tránh khỏi!
Nếu không muốn hối hận thì đừng làm, đã làm thì đừng hối hận!

ặc ặc bác nthdhsp đúng là cao thủ, bài 5 là India 95. Nhưng mà quy nạp ra thật sao? (Hay không cần quy nạp? , cách quy nạp liệu có đúng không? )
Bài 5 rất vui, bài của Erdös tất nhiên là thú vị rồi..
Em xin tiếp tục:
7/ (cũng Erdös nhá) Cho mn+1 số a1,...,amn+1. Cmr:
tồn tại hoặc m+1 số i1<...<im+1 để ai1<ai2<...<aim+1
hoặc n+1 số j1<...<jn+1 để aj1>aj2>....>ajn+1
(hình như Singapore có 1 bài là cho 100 số, tồn tại 12 số hoặc 10 số thoả mãn.... )
8/ A là tập con của tập {(t1,...,tn) / ti=0 hoặc 1 }
Biết |A|>2^(n+1)/n
Cmr: tồn tại t,r,s thuộc A sao cho
tồn tại đúng 2 i để ti khác ri
tồn tại đúng 2 j để rj khác sj
tồn tại đúng 2 k để sk khác tk
Huhu các bác giải giúp em với

Shinichi Kudo

Bài 3 thì yên tâm là quy nạp ra được.
Xem qua thì nhớ bài 7 làm theo kiểu đưa ra các dãy:
m11<m21<....<mk1
m12<m22<....<ml2
Vân vân. Sau phản chứng rồi lấy các cái cuối thì ra 1 dãy a1>a2>....>an+1
Cụ thể hơi dài dòng nên nói ngắn gọn thế thôi.
Bài 8 thì nhớ không nhầm là thế này. Mỗi u thuộc A. Xây dựng tập F(u) là tập hợp con n phần tử của {(t1,...,tn) / ti=0 hoặc 1 } mà các phần tử này chỉ có 1 chỉ số khác 1 chỉ số của u. Như vậy sẽ có 1 phần tử u của {(t1,...,tn) / ti=0 hoặc 1 } thuộc 3 cài F(t), F(r), F(s) nào đó. Khi đó thì dễ thấy t,r,s thoả mãn.

Life is ocean of misery!
Đã là phúc thì không phải là hoạ, đã là hoạ thì không tránh khỏi!
Nếu không muốn hối hận thì đừng làm, đã làm thì đừng hối hận!

Cám ơn về lời giải bài 7 và bài 8 của NHT
còn đây là bài 3 - cách giải ko quy nạp, mời các bạn tham khảo ( Ý tưởng chính là của dickchimney )
S={1,...,n}
Dễ thấy mỗi tập hợp Ai có thể tương đương với một vectơ ci=(ai1,...,ain), mỗi thành phần aij = 0 hoặc 1 tương ứng với j không thuộc Ai hay thuộc ai.
Các vectơ như vậy fân biệt. Bây giờ xét ma trận A=(aij) trên Z2:
Cách bỏ đi phần tử x chính là bỏ đi cột thứ x.
Đặt ri là vectơ gồm toàn 0, thành phần thứ i là 1
Phản chứng: ko tồn tại fần tử x thoả mãn, như vậy với mỗi i đều tồn tại 2 vectơ ck và cj để ck+cj=ri.
Như vậy có n bộ (ck,cj). Dễ thấy các bộ này phân biệt.
tương ứng mỗi vectơ ci với 1 đỉnh của đồ thị, ck nối với cj nếu (ck,cj) là 1 bộ được nói đến ở trên. Như vậy đồ thị có n đỉnh và n cạnh. Do đó tồn tại 1 đường đi khép kín (ci1,ci2),(ci2,ci3),...(cim,ci1).
Xét tổng các số này: ci1+ci2+...+cim+ci1 = rl1+rl2+...+rlm khác 0 trên Z2 ==> vô lý ==> đpcm!
Trông lời giải hơi dài dòng nhưng thực ra ý tưởng rất hay. Một lần nữa xin cảm ơn Dickchimney.

Shinichi Kudo

Được heroes sửa chữa / chuyển vào 23:57 ngày 23/09/2003

Thứ nhất. Tại hạ tên NHT.
Thứ hai: bài 3 tại hạ không dùng đến đồ thị nhưng dù sao cũng cảm ơn lời giải bằng đồ thị đó!
Thứ ba: Hiện tại hạ đang trong thời kỳ không đụng đến toán cấp 3.

Life is ocean of misery!
Đã là phúc thì không phải là hoạ, đã là hoạ thì không tránh khỏi!
Nếu không muốn hối hận thì đừng làm, đã làm thì đừng hối hận!

Bài này dùng LinearAlgebra
Gọi tổng tất cả là S
Mỗi dữ kiện " bỏ đi một số" là một pt dạng ai/2+ ai1+...+ain= S/2. Ma trận của hệ là ma trận đường chéo 1/2 còn lại toàn 0 và 1. Để cm det khác 0, các bác cứ nhân nó với 2 thì biết (sẽ ra det*2^n là số lẻ).
Suy ra hệ có nghiệm duy nhất la tất cả các ai bằng nhau!!
ĐPCM!!

Híc, bác Chimney lại làm đúng rồi. Sau 2 ngày vật lộn và bất lực với bài Toán của bác CXR (híc, bài đấy khó thật) , em có 2 bài mới này:
9) 2 vectơ A=(a1,...,an), B=(b1,...,bn), ai, bi đều nguyên không âm gọi là so sánh được hay A<=B nếu ai<=bi với mọi i.
s cho trước. Chứng minh rằng trong vô hạn vectơ luôn tìm được s thằng so sánh được với nhau.
10) 1 tập được gọi là tập góc nếu nó chứa 1 phần tử A=(a1,...,an) ai nguyên không âm thì nó chứa mọi phần tử B=(b1,...,bn) mà B<=A.
Cho vô hạn tập góc. Chứng minh rằng có 2 tập mà 1 tập là tập con của tập kia.

Shinichi Kudo