Problem:
Given an array of real numbers. You may change the sign of all numbers in a row or of all numbers in a column. Prove that by repeated changes you can obtain an array with all row and column sums non-negative.
All-Soviet-Union Mathematical Olympiad
Solution
Solution:
The array has 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 entries may be different. There are at most 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.
Want a route through all this instead of an archive? The track
puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.