Câu hỏi 38
Cho số nguyên $n\ge2$. Elwyn được cho một bảng $n\times n$ chứa các số thực, mỗi ô chứa đúng một số. Một tập xe là một tập gồm $n$ ô nằm trên $n$ hàng đôi một khác nhau và $n$ cột đôi một khác nhau. Giả sử với mọi tập xe, tổng $n$ số trong các ô của tập ấy đều không âm.
Trong mỗi nước đi, Elwyn chọn một hàng, một cột và một số thực $a$, rồi cộng $a$ vào mỗi số trong hàng được chọn và trừ $a$ khỏi mỗi số trong cột được chọn; vì vậy số tại giao điểm của hàng và cột không thay đổi. Chứng minh rằng Elwyn có thể thực hiện một dãy nước đi để mọi số trong bảng đều trở thành không âm.
Trong mỗi nước đi, Elwyn chọn một hàng, một cột và một số thực $a$, rồi cộng $a$ vào mỗi số trong hàng được chọn và trừ $a$ khỏi mỗi số trong cột được chọn; vì vậy số tại giao điểm của hàng và cột không thay đổi. Chứng minh rằng Elwyn có thể thực hiện một dãy nước đi để mọi số trong bảng đều trở thành không âm.