http://dientuvietnam.../mimetex.cgi?21 cô gái và http://dientuvietnam...n/mimetex.cgi?6 bài toán.
b)Với mỗi cặp một cô gái và một chàng trai,có ít nhất một bài toán mà cả hai người cùng làm được.
Chứng minh rằng có ít nhất một bài toán được giải bởi ít nhất http://dientuvietnam...n/mimetex.cgi?3 cô gái và ít nhất http://dientuvietnam...n/mimetex.cgi?3 chàng trai.
Nhìn lại tất cả các bài toán của China TST 2004
Mạnh hơn IMO2001-3
Bắt đầu bởi QUANVU, 19-03-2006 - 10:28
#1
Đã gửi 19-03-2006 - 10:28
1728
#2
Đã gửi 19-03-2006 - 16:44
Giả thiết phản chứng,với mỗi bài toán thì hoặc có <=2nam giải được nó hoặc có <=2 nữ giải được nó,ta đặt t.ư một bài toán là đỏ(xanh) nếu số nữ giải được nó >=(<=) 2.Bằng cách đó nếu nếu một bài toán được tô màu đỏ(xanh)thì số nam(nữ)giải được nó<=2.Lập bảng vuông 20 hàng và 21 cột;mỗi ô (i;j)viết số của bài toán mà B_i và G_j giải được
Nếu có >=210 ô xanh thì theo nguyên lí dirichle có nhất 1 hàng(ứng với B_i) có>=11 ô tô màu xanh->B_i giải được đúng 6 bài toán đó->số cô gái giải ít nhất một bài toán với B_i<=12->vô lí
Ngược lại có >210 ô được tô màu đỏ;->tồn tại một cột có chứa >=11 ô đỏ;ta có mâu thuẫn tương tự như trên
Chú ý nếu thay bằng bảng 20*20 thì bài toán không đúng
Nếu có >=210 ô xanh thì theo nguyên lí dirichle có nhất 1 hàng(ứng với B_i) có>=11 ô tô màu xanh->B_i giải được đúng 6 bài toán đó->số cô gái giải ít nhất một bài toán với B_i<=12->vô lí
Ngược lại có >210 ô được tô màu đỏ;->tồn tại một cột có chứa >=11 ô đỏ;ta có mâu thuẫn tương tự như trên
Chú ý nếu thay bằng bảng 20*20 thì bài toán không đúng
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh