а) Пример. Если расставить числа так, как показано в таблице, – сначала заполнить первые k столбцов, строку за строкой, числами от 1 до kn, а затем оставшимися числами заполнить последние  n – k  столбцов (как угодно, лишь бы выполнялось условие возрастания чисел в каждой строке) – то сумма чисел в k-м столбце будет равна  ½ kn(n + 1).

  Оценка. Пусть  a₁, a₂, ..., a_n  – числа k-го столбца, занумерованные в порядке возрастания:  a₁ < a₂ < ... < a_n.  Рассмотрим числа, стоящие в тех же строках, где стоят  a₁, a₂, ..., a_i,  и в первых k столбцах. Эти ki чисел не превосходят a_i, поэтому  a_i   k_ii = 1, 2, ..., n,  получим

a₁ + a₂ + ... + a_n ≥ ½ kn(n + 1).   б) Заменим в таблице каждое число a на  (n² + 1 – a)  и затем переставим числа в каждой строке в обратном порядке. Ясно, что это – взаимно однозначное преобразование множества таблиц из чисел 1, 2, ..., n², удовлетворяющих условию задачи. При этом преобразовании каждое число в k-м столбце новой таблицы A'  равно числу в той же строке и в (n+1–k)-м столбце старой таблицы A; поэтому сумма чисел в k-м столбце таблицы A'  равна  n(n² + 1) – S,  где S – сумма чисел в  (n+1–k)-м столбце A. Так что достаточно решить задачу а) для столбца с номером  n + 1 – k.  Следовательно, максимальная сумма в k-м столбце равна  n(n² + 1) – ½ (n + 1 – k)n(n + 1) = ½ n((n – 1)² + k(n + 1)).

а)  ½ kn(n + 1);   б)  ½ n((n – 1)² + k(n + 1)).