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

[ngoctuan]

n N* , chia 3n số {1,2,3......,3n} thành 3 tập A,B,C mỗi tập n số. cmr luôn tìm đc a A ,b B ,c C sao cho trong 3 số này có 1 số bằng tổng 2 số kia.

[lvd]

Giả sử ta có thể tìm được một phân hoạch thỏa mãn a=b+c vô nghiệm(a,b,c thuộc 3 tập phân biệt);không mất tổng quát giả sử Gọi k là số nhỏ nhất ko thuộc A,giả sử thuộc B .Giả sử .Ta chứng minh ,từ đó suy ra mâu thuẫn.
Thật vậy ,nếu ->x-1>k.Xét các bộ (x-k;k;x);(k-1;x-k;x-1),các số trong mỗi bộ không thể thuộc 3 tập phân biệt,ta suy ra được x-k thuộc C.Tương tự xét các bộ (x-k-1;k;x-1) và (1;x-k-1;x-k),ta thấy x-k-1 thuộc C.
Bằng quy nạp ta chứng minh được x-ik và x-ik-1 thuộc C.Với i đủ lớn điều này mâu thuẫn

Bài viết đã được chỉnh sửa nội dung bởi lvd: 18-02-2006 - 15:44

[lehoan]

Bài toán mạnh hơn.

Giả sử tập http://dientuvietnam.net/cgi-bin/mimetex.cgi?\{1;2;...;n\} được chia thành 3 tập http://dientuvietnam.net/cgi-bin/mimetex.cgi?>\dfrac{n}{4}. Chứng minh rằng tồn tại http://dientuvietnam...metex.cgi?a;b;c bằng tổng quả 2 số còn lại. Đây là bài toán rất khó

[dhkhtn-tnt]

Mình biết 1 kqua khác rất thú vị:
Cho http://dientuvietnam.net/cgi-bin/mimetex.cgi?A=\{1,2,..n\}
Cm tồn tại 1 tập con của A là S sao cho:http://dientuvietnam.net/cgi-bin/mimetex.cgi?|S|\geq\dfrac{n}{3} và trong http://dientuvietnam...n/mimetex.cgi?S thì ko có 3 số nào t/m:http://dientuvietnam.net/cgi-bin/mimetex.cgi?a+b=c
Cm cái này thì sd 1 nguyên lí khá hiển nhiên n0 theo mình là mới!

[lehoan]

Ở bài toán của dhkhtn-tnt theo mình thì phải xét theo http://dientuvietnam.net/cgi-bin/mimetex.cgi?[\dfrac{n}{2}]-1 phần tử .

Và khi đó ta có bài toán tổng quát

Cho số nguyên dương http://dientuvietnam...mimetex.cgi?T_n là số nhỏ nhất để tồn tại tập gồm http://dientuvietnam...mimetex.cgi?T_n phần tử thuộc đoạn http://dientuvietnam....cgi?[1;n] sao cho không có 3 số http://dientuvietnam...metex.cgi?a;b;c thuộc http://dientuvietnam...n/mimetex.cgi?S nào mà http://dientuvietnam...metex.cgi?a;b;c không nhất thiết phân biệt)

a) CMR nếu http://dientuvietnam...n/mimetex.cgi?n chẵn thì http://dientuvietnam.net/cgi-bin/mimetex.cgi?T_n=\dfrac{n}{2}.
b) CMR nếu http://dientuvietnam...n/mimetex.cgi?n lẻ thì http://dientuvietnam.net/cgi-bin/mimetex.cgi?T_n=[\dfrac{n}{3}]+1 khi và chỉ khi http://dientuvietnam.net/cgi-bin/mimetex.cgi?n=p hoặc http://dientuvietnam.net/cgi-bin/mimetex.cgi?n=3p với http://dientuvietnam.net/cgi-bin/mimetex.cgi?p là số nguyên tố có dạng http://dientuvietnam.net/cgi-bin/mimetex.cgi?3k+2.

@: Câu c) rất khó

Thêm một bài toán dạng này:

Chứng minh rằng với http://dientuvietnam.net/cgi-bin/mimetex.cgi?n số nguyên dương phân biệt tùy ý ta có thể tìm được ít nhất http://dientuvietnam.net/cgi-bin/mimetex.cgi?\dfrac{n}{3} số mà không có số nào bằng tổng của 2 số còn lại. ( Không nhất thiết phân biệt)

[FDF]

TST Mĩ 2001,chắc dhkhtn-tnt muốn nói tới nguyên lí xác xuất;cái này không đơn giản đâu-bạn nào quan tâm có thể xem ở đây:
http://encyclopedia......listic method

[dhkhtn-tnt]

Mình biết 1 kqua khác rất thú vị:
Cho http://dientuvietnam.net/cgi-bin/mimetex.cgi?A=\{1,2,..n\}
Cm tồn tại 1 tập con của A là S sao cho:http://dientuvietnam.net/cgi-bin/mimetex.cgi?|S|\geq\dfrac{n}{3} và trong http://dientuvietnam...n/mimetex.cgi?S thì ko có 3 số nào t/m:http://dientuvietnam.net/cgi-bin/mimetex.cgi?a+b=c
Cm cái này thì sd 1 nguyên lí khá hiển nhiên n0 theo mình là mới!

Mình viết nhầm http://dientuvietnam.net/cgi-bin/mimetex.cgi?A=\{a_1,a_2,..,a_n\}

[dhkhtn-tnt]

[quote name='lvd' date='Feb 7 2006, 03:23 PM'] .Ta chứng minh http://dientuvietnam...mimetex.cgi?x-k có thể thuộc B,http://dientuvietnam.net/cgi-bin/mimetex.cgi?k-1 thuộc C

[lvd]

Xin lỗi tớ post hơi tắt
Ta đã giả sử k là số min không thuộc A->k-1 thuộc A
Ta đã chứng minh được với mọi ;;hơn nữa
Vậy nếu C={x_1;...x_n} thì A chứa n+1 phần tử phân biệt 1;x_1-1...x_n-1-> vô lí

[chien_tuynh]

hình như bài này trong quyển tuyển tập các bài toán dự tuyển quốcn ttế

[hiepkhach7488]

[SIZE=1] Cac bac co bao nhieu nguoi trung de.Cac doi khac lam tot nhu ay sao

[duongthudao]

Bài này ông Thầy mình cũng đã chữa.Nói chung là gần như suy luận logic