Problème de combinatoire basé sur un algorithme, style IMO [duplicate]
Le problème est décrit dans l'image, la solution est supposée être une preuve constructive, vous devez donc trouver un algorithme qui fonctionne indépendamment de choses comme le temps d'exécution. Toute aide serait reconnaissante, je ne peux pas résoudre ça et j'essaye depuis un moment

EDIT: Ma direction principale était de changer le signe sur chaque brut avec une somme négative, maintenant chaque brut est complet et la somme de toutes les entrées est non négative (puisque la somme de toutes les matières brutes est maintenant non négative)
Réponses
Si une ligne ou une colonne a une somme négative, choisissez-en une et inversez les signes.
Répétez le processus.
Après chaque transition, la somme de toutes les entrées de la matrice est augmentée.
Mais la valeur absolue des entrées reste inchangée, il n'y a donc que des possibilités infinies pour la somme totale.
Il s'ensuit que le processus finira par se terminer.
Utilisez simplement l'algorithme simple suivant: À chaque tour, inversez les signes d'une ligne ou d'une colonne aléatoire avec une somme négative et nous prouverons que cette procédure se termine par des mouvements finis: Notez qu'en utilisant cet algorithme, la somme des nombres dans tous les board augmentera toujours et parce que cette somme est bornée par le haut et qu'il y a aussi des possibilités finies pour cette somme, notre algorithme s'arrêtera quelque part et il y a le point que la somme de toutes les lignes et colonnes est non négative.