Problema de combinatoria basado en algoritmos estilo IMO [duplicado]
El problema se describe en la imagen, se supone que la solución es una prueba constructiva, por lo que necesita encontrar un algoritmo que funcione independientemente de cosas como el tiempo de ejecución. Cualquier ayuda sería agradecida.No puedo resolver esto y lo he intentado por un tiempo.
EDITAR: Mi dirección principal fue cambiar el signo en cada crudo con suma negativa, ahora cada crudo está completo y la suma de todas las entradas no es negativa (ya que la suma de todos los crudos ahora no es negativa)
Respuestas
Si alguna fila o columna tiene una suma negativa, elija una e invierta los signos.
Itere el proceso.
Después de cada transición, se incrementa la suma de todas las entradas de la matriz.
Pero el valor absoluto de las entradas permanece sin cambios, por lo que solo hay un número finito de posibilidades para la suma total.
De ello se deduce que el proceso terminará finalmente.
Simplemente use el siguiente algoritmo simple: En cada turno, invierta los signos de una fila o columna aleatoria con suma negativa y probaremos que este procedimiento termina en movimientos finitos: Tenga en cuenta que al usar este algoritmo, la suma de números en todos los tablero siempre aumentará y debido a que esta suma está acotada desde arriba y también hay posibilidades finitas para esta suma, nuestro algoritmo se detendrá en algún lugar y llegará el punto en que la suma de todas las filas y columnas no es negativa.