Bài toán tổ hợp dựa trên thuật toán Kiểu IMO [trùng lặp]

Question

Vấn đề được mô tả trong hình, giải pháp được cho là một bằng chứng mang tính xây dựng, vì vậy bạn cần tìm một thuật toán hoạt động bất kể những thứ như thời gian chạy. Mọi sự giúp đỡ sẽ rất biết ơn Tôi không thể giải quyết vấn đề này và tôi đã cố gắng một thời gian

CHỈNH SỬA: Hướng chính của tôi là thay đổi dấu hiệu trên mọi dữ liệu thô bằng tổng âm, bây giờ mọi dữ liệu thô đã hoàn thành và tổng của tất cả các mục nhập là không âm (vì tổng của tất cả các dữ liệu thô bây giờ là không âm)

Answer 1

Nếu bất kỳ hàng hoặc cột nào có tổng âm, hãy chọn một và đảo ngược các dấu hiệu.

Lặp lại quy trình.

Sau mỗi lần chuyển đổi, tổng của tất cả các mục trong ma trận được tăng lên.

Nhưng giá trị tuyệt đối của các mục không thay đổi, do đó chỉ có rất nhiều khả năng cho tổng tổng.

Quá trình này cuối cùng sẽ kết thúc.

Answer 2

Chỉ cần sử dụng thuật toán đơn giản sau: Trong mỗi lượt, đảo ngược các dấu hiệu của một hàng hoặc cột ngẫu nhiên có tổng âm và chúng tôi sẽ chứng minh rằng thủ tục này kết thúc bằng các bước di chuyển hữu hạn: Lưu ý rằng bằng cách sử dụng thuật toán này, tổng các số trong tất cả bảng sẽ luôn tăng và bởi vì tổng này được giới hạn từ phía trên và cũng có khả năng hữu hạn cho tổng này, thuật toán của chúng ta sẽ dừng lại ở đâu đó và có điểm là tổng của tất cả các hàng và cột là không âm.