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

[cuongcute1234]

Cho bảng m x n, mỗi ô ghi 1 số nguyên dương bất kỳ. cho phép thực hiên 1 trong 2 biến đổi

a) Nhân tất cả các số 1 hàng với 2

b)Trừ tất cả các số 1 cột cho 1

Hỏi sau hữu hạn các bước có đưa bảng về toàn số 0 hay không ?

Bài viết đã được chỉnh sửa nội dung bởi cuongcute1234: 25-11-2013 - 12:54

[dinhthanhhung]

Bài này đề đúng là thực hiện các bước a,b so le nhau . Nếu không thì sẽ rất lộn xộn (!)

Lời giải :

Ta thấy sau khi nhân đôi một hàng nào đó , rồi trừ một cột nào đó thì trên bảng sẽ có ít nhất một số lẻ .

Do vậy bước cuối cùng là bước nhân đôi các số trong một hàng .

Mặt khác sau khi nhân , ta được bảng toàn số 0 , vậy bước đó không thay đổi gì cả .

Điều này đưa ta tới kết luận là bảng ban đầu phải có số 0 , điều này vô lí với giả thiết .

Vậy không tồn tại hữu hạn buớc .

[dinhthanhhung]

Bài này đề đúng là thực hiện các bước a,b so le nhau . Nếu không thì sẽ rất lộn xộn (!)

Lời giải :

Ta thấy sau khi nhân đôi một hàng nào đó , rồi trừ một cột nào đó thì trên bảng sẽ có ít nhất một số lẻ .

Do vậy bước cuối cùng là bước nhân đôi các số trong một hàng .

Mặt khác sau khi nhân , ta được bảng toàn số 0 , vậy bước đó không thay đổi gì cả .

Điều này đưa ta tới kết luận là bảng ban đầu phải có số 0 , điều này vô lí với giả thiết .

Vậy không tồn tại hữu hạn buớc .

 

Xin lỗi vì đã chém đề =)) Hôm nay nghĩ lại thì với điều kiện như bạn đã cho , ta có lời giải như sau :

Xét một cột và các ô chứa số 1 nằm trên hàng đó ta nhân hai các hàng tương ứng sau đó trừ 1 cột đó đi ( đến khi xuất hiện số 1 thì thôi ) , nếu không có số 1 nào thì ta trừ 1 . Dễ thấy tổng của tất cả các số sẽ giảm sau các biến đổi , đồng thời các biến đổi đảm bảo không có số nào thành số 0 . Do đó đến một lúc nào đấy cột đó sẽ toàn số 1 và lúc này trừ 1 đi ta được toàn số 0.

Thực hiện lần lượt trên các cột , có được bảng toàn số 0.