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


			
Назовем циклическим сдвигом такое преобразование таблицы:
  первый столбец переставляется на место второго, второй -
  на место третьего, и т.д., наконец, последний - на место первого.
  Обозначим через s0 сумму чисел,
  стоящих на диагонали таблицы, через s1
  сумму чисел, которые попадут на диагональ после
  циклического сдвига, и вообще, через
  sk сумму чисел, которые попадут на диагональ,
  если проделать циклический сдвиг k раз.
  Ясно, что сумма всех чисел в таблице равна
  s=s0+s1+...+sn-1, потому что
  если проделать циклический сдвиг 0,1,...,n-1 раз,
  то за это время каждое число побывает на диагонали ровно однажды.
  По условию s неотрицательно, следовательно,
  некоторое sk
  неотрицательно. Проделав циклический сдвиг k раз,
  мы получим требуемую перестановку столбцов.
			
Подсчет двумя способами