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

[HUYVAN]

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.

[manutd]

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.

[leecom]

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ỉ?

[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 .

[manutd]

Mình chưa hiểu chỗ này. Có 2 cặp số tốt thì sao nhỉ?

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á!

[manutd]

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 .

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?

[thangde.]

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