Algorithmusbasiertes kombinatorisches Problem IMO-Stil [Duplikat]
Das Problem ist im Bild beschrieben. Die Lösung soll ein konstruktiver Beweis sein. Sie müssen also einen Algorithmus finden, der unabhängig von der Laufzeit funktioniert. Jede Hilfe wäre dankbar, dass ich das nicht lösen kann und es eine Weile versucht habe
BEARBEITEN: Meine Hauptrichtung war das Ändern des Vorzeichens bei jedem Rohwert mit negativer Summe. Jetzt ist jeder Rohwert vollständig und die Summe aller Einträge ist nicht negativ (da die Summe aller Rohdaten jetzt nicht negativ ist.)
Antworten
Wenn eine Zeile oder Spalte eine negative Summe hat, wählen Sie eine aus und kehren Sie die Vorzeichen um.
Iterieren Sie den Prozess.
Nach jedem Übergang wird die Summe aller Einträge in der Matrix erhöht.
Der absolute Wert der Einträge bleibt jedoch unverändert, so dass es nur endlich viele Möglichkeiten für die Gesamtsumme gibt.
Daraus folgt, dass der Prozess schließlich beendet wird.
Verwenden Sie einfach den folgenden einfachen Algorithmus: Kehren Sie in jeder Runde die Vorzeichen einer zufälligen Zeile oder Spalte mit einer negativen Summe um und wir werden beweisen, dass diese Prozedur in endlichen Zügen endet: Beachten Sie, dass Sie mit diesem Algorithmus die Summe der Zahlen in allen verwenden Board wird immer größer und da diese Summe von oben begrenzt ist und es auch endliche Möglichkeiten für diese Summe gibt, wird unser Algorithmus irgendwo anhalten und es gibt den Punkt, dass die Summe aller Zeilen und Spalten nicht negativ ist.