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

[lovePearl_maytrang]

Đã từ lâu rồi (cũng không nhớ nữa) mình có đọc bài toán sau:
Cho bảng vuông 9*9, trên mỗi hình vuông đơn vị viết một chữ số (0,...,9) sao cho các số được tạo thành trên các hàng ngang là đôi một khác nhau. Chứng minh rằng ta có thể xóa đi một cột nào đó để các số tạo thành trên các hàng (sau khi xóa đi) vẫn còn đôi một khác nhau...
Để chứng minh bài toán đó, sau nhiều lần đi vòng vèo, em chợt nghĩ ra bài toán sau: tổng quát thay hình vuông 9*9 bằng một bảng chữ nhật bất kì với kích thước m*n (m cột, n hàng) trong đó m n 2.
Nhờ các bạn kiểm tra thử xem kết quả này có đúng không?

DDTH

[MrMATH]

bài này đúng đó, có điều chứng minh hơi phức tạp, phải có tư duy về đồ thi tốt mai ra mới làm được, mà cần thêm 1 bổ đề nữa, tự nhiên quên mất, các bạn suy nghĩ thêm nhé.okie?

[lovePearl_maytrang]

Thực ra thì bài toán đầu được lấy từ trong cuốn sách "Graph hữu hạn" của anh Vũ Đình Hòa. Lời giải trong đó được minh họa cho phương pháp dùng đồ thị, và bổ đề mà bạn nói có phải là: nếu đồ thị hữu hạn có n đỉnh và có ít nhất n cạnh thì có ít nhất một chu trình. Nhưng ý chính tớ muốn thảo luận là đề toán thứ hai kia...

[lovePearl_maytrang]

Tớ xin mạn phép đưa ra cách giải cho đề toán thứ hai như sau:
Với bảng chữ nhật m*n gồm m cột và n hàng , m n, ta chứng minh qui nạp theo n như sau:
-Các bạn tự kiểm tra với n=2
-Giả sử bài toán đã đúng với mọi số tự nhiên <n
-Xét bảng n hàng, m cột. Đánh số các hàng và các cột từ trên xuống dưới và từ trái sang phải. Ta xóa đi cột 1. Nếu các số tạo được ở các hàng lúc này đôi một khác nhau thì không còn gì phải chứng minh. Nếu có nhưng nhóm hàng nào đó giống nhau. Thế thì tại mỗi nhóm giống nhau đó, ta chỉ giữ lại một đại diện và xóa đi tất cả các hàng còn lại. Lúc này có hai trường hợp:
+Nếu sau khi thực hiện các bước này bảng chỉ còn lại một hàng duy nhất: trường hợp này các bạn tự suy nghĩ.
+Nếu còn lại k 2 hàng. Khi đó bảng còn lại có m-1 cột và k hàng, 2 k n-1, nên k m-1. Áp dụng giả thiết qui nạp cho bảng này. Bài toán được chứng minh
Một trong các trường hợp đặck biệt của bài này là m=n=9...

[bolzano]

Em có bài tương tự này:
x1,x2,...,xm,y1,y2,...,yn N
x1+x2+...xm=y1+y2+...yn <mn
Cm trong đẳng thức trên có thể bỏ đi vài số hạng mà vẫn giữ được dấu đẳng thức.