Αθροίσματα σε πίνακα

#1

Σε κάθε κελί ενός $m \times n$ πίνακα είναι γραμμένος ένας αριθμός. Σε κάθε κίνηση επιτρέπεται να αλλάξετε το πρόσημο όλων των αριθμών μιας σειράς ή όλων των αριθμών μιας στήλης.

Να δειχθεί ότι μπορείτε να κάνετε μια ακολουθία κινήσεων ώστε εν τέλει το άθροισμα των αριθμών κάθε σειράς και το άθροισμα των αριθμών κάθε στήλης να είναι μη αρνητικό.

Πηγή: Σοβιετική Ένωση 1961

#2

Πρόκειται για κλασική εφαρμογή της "Αρχής του Μεγίστου Στοιχείου".

Έστω $\displaystyle{{a_{ij}}}$ ο αριθμός που είναι γραμμένος στο κελί $\displaystyle{\left( {i,j} \right)}$ του πίνακα (όπου $\displaystyle{i \in \left\{ {1,2, \ldots ,m} \right\}}$ και $\displaystyle{j \in \left\{ {1,2, \ldots ,n} \right\}}$ ).

Σε κάθε πίνακα που προκύπτει από τον αρχικό μετά από μια ακολουθία επιτρεπτών κινήσεων, στο κελί $\displaystyle{\left( {i,j} \right)}$ μπορεί να είναι γραμμένος είτε ο αριθμός $\displaystyle{{a_{ij}}}$ είτε ο $\displaystyle{-{a_{ij}}.}$ Επομένως, ο συνολικός αριθμός των πινάκων που μπορεί να προκύψουν είναι το πολύ ίσος με $\displaystyle{{2^{mn}}}$ - δηλαδή είναι πεπερασμένος.

Επομένως, υπάρχει πίνακας $\displaystyle{M}$ (που προκύπτει από τον αρχικό μετά από μια ακολουθία επιτρεπτών κινήσεων) τέτοιος, ώστε το άθροισμα των στοιχείων του να είναι μέγιστο. Ισχυριζόμαστε ότι ο πίνακας $\displaystyle{M}$ έχει τη ζητούμενη ιδιότητα. Πράγματι, αν το άθροισμα των αριθμών μιας γραμμής ή στήλης του $\displaystyle{M}$ είναι αρνητικό, τότε αλλάζοντας το πρόσημο όλων των αριθμών της γραμμής ή της στήλης αυτής προκύπτει ένας πίνακας $\displaystyle{{M'}}$ με άθροισμα στοιχείων μεγαλύτερο από αυτό του $\displaystyle{M,}$ πράγμα άτοπο.

Αθροίσματα σε πίνακα

Αθροίσματα σε πίνακα

Re: Αθροίσματα σε πίνακα

Μέλη σε σύνδεση