Полуинвариант

Рассмотрим величину равную сумме всех произведений вида где числа и стоят в соседних клетках. Пусть мы пока не добились необходимого условия на знаки. Тогда есть число сумма его соседей имеет тот же знак: (неравенство строгое, поскольку числа целые(но ненулевые), а сумма не Тогда поменяем знак у Теперь а, значит, вся величина тоже уменьшилась. Она ограничена снизу(возьмём все слагаемые из со знаком минус и получим минимум), поэтому процесс остановится, и мы получим расстановку, требуемую в условии.