Trong mỗi ô vuông của một hình vuông 9.9 được ghi 1 chữ số sao cho các số được tạo thành trên mỗi dòng đôi một khác nhau. C/m: ta có thể bỏ đi một cột sao cho các số được tạo thành trên mỗi dòng vẫn còn đôi một khác nhau.
Tổ hợp
Bắt đầu bởi HUYVAN, 01-08-2006 - 09:09
#1
Đã gửi 01-08-2006 - 09:09
#2
Đã gửi 02-08-2006 - 08:40
Ta gọi một cặp số tốt http://dientuvietnam...imetex.cgi?(a,b) là cặp số thoả mãn các điều kiện sau:
1. http://dientuvietnam...n/mimetex.cgi?a khác http://dientuvietnam.../mimetex.cgi?b.
2. Nằm trên hai ô kề nhau của cùng một cột.
3. Nếu bỏ đi cột chứa hai số đó thì số tạo thành trên hai hàng tương ứng với hai số đó trở thành giống nhau.
Từ đó ta có nhận xét, mỗi cặp dòng có không quá 1 cặp số tốt.
Cần chứng minh tồn tại một cột không chứa bất kì một cặp số tốt nào. Thật vậy, nếu điều đó không xảy ra tức là mỗi cột có ít nhất một cặp số tốt thì trên bảng có ít nhất 9 cặp số tốt. Xét 9 dải ngang 2.9 trên bảng, ắt tồn tại một dải có hai cặp số tốt. Mâu thuẫn với nhận xét cho ta ĐPCM.
1. http://dientuvietnam...n/mimetex.cgi?a khác http://dientuvietnam.../mimetex.cgi?b.
2. Nằm trên hai ô kề nhau của cùng một cột.
3. Nếu bỏ đi cột chứa hai số đó thì số tạo thành trên hai hàng tương ứng với hai số đó trở thành giống nhau.
Từ đó ta có nhận xét, mỗi cặp dòng có không quá 1 cặp số tốt.
Cần chứng minh tồn tại một cột không chứa bất kì một cặp số tốt nào. Thật vậy, nếu điều đó không xảy ra tức là mỗi cột có ít nhất một cặp số tốt thì trên bảng có ít nhất 9 cặp số tốt. Xét 9 dải ngang 2.9 trên bảng, ắt tồn tại một dải có hai cặp số tốt. Mâu thuẫn với nhận xét cho ta ĐPCM.
không thể online nhiều được nữa, hẹn gặp lại diễn đàn trong một ngày gần đây
#3
Đã gửi 02-08-2006 - 11:07
Từ đó ta có nhận xét, mỗi cặp dòng có không quá 1 cặp số tốt.
Mình chưa hiểu chỗ này. Có 2 cặp số tốt thì sao nhỉ?
The Past, The Present, and The Future...
#4
Đã gửi 02-08-2006 - 12:06
CMTQ cho n.n
Quy nạp:
nếu bỏ 1 cột đi mà các dòng chưa pb , ta lấy 1 dòng làm đại diện và bỏ các dòng giống với nó đi.khi đó ta sẽ có 1 bảng k.(n-1) với k<=n-1 .Theo gt quy nạp tồn tại 1 cột mà khi bỏ đi các dòng sẽ pb ,kết hợp với gt các dòng pb ngay từ đầu ta có đpcm.
Có thể TQ cho bảng m.n .
Quy nạp:
nếu bỏ 1 cột đi mà các dòng chưa pb , ta lấy 1 dòng làm đại diện và bỏ các dòng giống với nó đi.khi đó ta sẽ có 1 bảng k.(n-1) với k<=n-1 .Theo gt quy nạp tồn tại 1 cột mà khi bỏ đi các dòng sẽ pb ,kết hợp với gt các dòng pb ngay từ đầu ta có đpcm.
Có thể TQ cho bảng m.n .
#5
Đã gửi 02-08-2006 - 16:23
Cái này dựa vào định nghĩa cặp số tốt thôi, bạn xem kĩ lại đi nhá!Mình chưa hiểu chỗ này. Có 2 cặp số tốt thì sao nhỉ?
không thể online nhiều được nữa, hẹn gặp lại diễn đàn trong một ngày gần đây
#6
Đã gửi 02-08-2006 - 16:30
Sao lúc đầu nói là quy nạp cho bảng n.n mà sau đó lại xuất hiện bảng k.(n-1) là sao đây hả anhhong?CMTQ cho n.n
Quy nạp:
nếu bỏ 1 cột đi mà các dòng chưa pb , ta lấy 1 dòng làm đại diện và bỏ các dòng giống với nó đi.khi đó ta sẽ có 1 bảng k.(n-1) với k<=n-1 .Theo gt quy nạp tồn tại 1 cột mà khi bỏ đi các dòng sẽ pb ,kết hợp với gt các dòng pb ngay từ đầu ta có đpcm.
Có thể TQ cho bảng m.n .
không thể online nhiều được nữa, hẹn gặp lại diễn đàn trong một ngày gần đây
#7
Đã gửi 02-08-2006 - 16:31
giả sử phản chứng bỏ cột i thì tồn tại 2 hàng giống nhau->2 hàng chỉ khác nhau ở duy nhất vị trí i
Xét đồ thị có n đỉnh a_1...a_n;a_i nối với a_j nếu 2 hàng chỉ khác nhau ở 1 vị trí;có
số đỉnh nhỏ hơn số cạnh nên tồn tại 1 chu trình.Từ đó dễ suy ra vô lí
Chứng minh quy nạp như anhhong cũng hay
Xét đồ thị có n đỉnh a_1...a_n;a_i nối với a_j nếu 2 hàng chỉ khác nhau ở 1 vị trí;có
số đỉnh nhỏ hơn số cạnh nên tồn tại 1 chu trình.Từ đó dễ suy ra vô lí
Chứng minh quy nạp như anhhong cũng hay
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh