Олимпиадная задача: нахождение суммы чисел в таблице без повторений строк и столбцов

Представим нашу таблицу как сумму двух таблиц:

Выбранные числа также "распадутся" в суммы соответствующих чисел в этих двух таблицах. При этом в первой таблице сумма соответствующих чисел равна  0 +a+ 2a+ ... +(a– 1)a= ½a²(a– 1)  (так как числа расположены по одному в каждой строке), а во второй –  1 + 2 + ... +a= ½a(a+ 1)  (так как числа расположены по одному в каждом столбце). Общая же сумма равна  ½a²(a– 1) + ½a(a+ 1) = ½a(a² + 1).

½ a(a² + 1).