Masalah kombinatorik berbasis algoritme gaya IMO [duplikat]
Masalahnya dijelaskan dalam gambar, solusinya dianggap sebagai bukti konstruktif, jadi Anda perlu menemukan algoritme yang berfungsi terlepas dari hal-hal seperti waktu berjalan. Bantuan apa pun akan sangat bersyukur. Saya tidak bisa menyelesaikan ini dan saya sudah mencoba untuk sementara waktu
EDIT: Arah utama saya adalah mengubah tanda pada setiap mentah dengan jumlah negatif, sekarang setiap mentah sudah lengkap dan jumlah semua entri tidak negatif (karena jumlah semua mentah sekarang nonnegatif)
Jawaban
Jika ada baris atau kolom yang memiliki jumlah negatif, pilih satu dan balikkan tandanya.
Ulangi prosesnya.
Setelah setiap transisi, jumlah semua entri dalam matriks bertambah.
Tetapi nilai absolut dari entri tetap tidak berubah, oleh karena itu hanya ada banyak kemungkinan untuk jumlah total.
Oleh karena itu, proses tersebut pada akhirnya akan berhenti.
Cukup gunakan algoritme sederhana berikut: Di setiap belokan, balikkan tanda baris atau kolom acak dengan jumlah negatif dan kami akan membuktikan bahwa prosedur ini berakhir dengan gerakan terbatas: Perhatikan bahwa dengan menggunakan algoritme ini, jumlah angka di semua papan akan selalu bertambah dan karena jumlah ini dibatasi dari atas dan juga ada kemungkinan terbatas untuk jumlah ini, algoritme kami akan berhenti di suatu tempat dan ada poin bahwa jumlah semua baris dan kolom adalah non-negatif.