board 2000×2000 with 1 and -1
Source: All-Russian olympiad 1995, Grade 9, Second Day, Problem 8
October 21, 2013
combinatoricsgraph theory
Problem Statement
Numbers 1 and −1 are written in the cells of a board 2000×2000. It is known that the sum of all the numbers in the board is positive. Show that one can select 1000 rows and 1000 columns such that the sum of numbers written in their intersection cells is at least 1000.
D. Karpov