Some Sum Signs:

Given an arbitary m x n array of reals. You may change the sign of all
the numbers in a row or of all the numbers in a column. Prove that by
repeated changes you can obtain an array with all row and column sums
non-negative.


























HINT:

Look for a potential function.





























SOLUTION:

The array has mn entries. Call an array that can be obtained by repeated
changes a reachable array. A reachable array differs from the original
only in that some or all of the signs of its mn entries may be
different. There are at most 2 possibilities for each sign (some entries
may be zero) and hence at most 2^mn different reachable arrays. For each
reachable array calculate the sum of all its entries. Take the reachable
array with the largest such sum. It must have non-negative row and
column sums, because if any such sum was negative, changing the sign of
that row or column would give another reachable array with strictly
greater total sum.

References:

Rainer Bodendiek, Gustav Burosch;
Streifz\"uge durch die Kombinatorik,
Aufgaben und L\"osungen aus dem Schatz der Mathematik-Olympiaden,
(Excursions into Combinatorics)
Spektrum Akademischer Verlag, Heidelberg, 1995,
ISBN 3-86025-393-X
Kapitel: Methode der Potentiale, Aufgabe 4.2