Комбинаторика на КФУ

Сначала рассмотрим “крайнюю” ситуацию. Если во всех клетках таблицы числа равны то и все произведения равны а их общая сумма равна

Если мы сменим знак в одной из клеток, то изменится знак в произведении чисел одной строки и одного столбца. Значит, сумма всех произведений изменится на величину то есть это изменение может равняться или Таким образом, после замены знаков в нескольких клетках таблицы значение суммы может измениться лишь на слагаемое, кратное

Взяв за основу таблицу, заполненную числами и меняя знаки в соответствующих клетках (чтобы придти к исходной таблице), мы получим значение суммы Наименьшее неотрицательное значение выражения очевидно, равно и оно достигается при целом

Осталось привести пример таблицы, для которой указанное значение суммы произведений равно Расставим сначала во всех клетках таблицы числа а затем заменим знак на у чисел, стоящих, например, на диагонали, идущей из левого верхнего угла в нижний. Для полученной таблицы сумма всех произведений равна