Максимальное значение суммы

[Tiberium]

Цитата:

Рассмотрим матрицу размера $2017 \times 2017$ , содержащую числа $1,2, ...., 2017^{2}$. Числа в ней записаны в порядке начиная с левого верхнего угла, двигаясь по строкам слева направо и сверху вниз, т.е. первое число, записанное во второй строке, равно $2018$. В этой матрице выбрано 2017 чисел так, что в каждой строке и каждом столбце выбрано ровно одно число.
Найдите максимальное значение, которое может принимать сумма этих чисел.

Скорее всего, тут есть какой-то хитрый подход, но я пошел прямолинейным путем — рассмотрел сначала матрицу $2 \times 2$, затем $3 \times 3$. Интуитивно кажется, что все просто, и сумма элементов, стоящих на главной диагонали матрицы, как раз и будет максимальной. То есть максимальная сумма для квадратной матрицы размера $n \times n$ равна $\frac{n(n^{2}+1)}{2}$.

Можно ведь здесь применить индукцию? И вообще, может, как-то иначе нужно рассуждать.

[thething]

Надо начать с того, чтобы понять постановку этой задачи, а то вот это

Tiberium в сообщении #1332859 писал(а):

Рассмотрим матрицу размера $2017 \times 2017$ , содержащую числа $1,2, ...., 2017$

и это

Tiberium в сообщении #1332859 писал(а):

первое число, записанное во второй строке, равно $2018$

одновременно я не понимаю. Также непонятен вопрос. Сумму каких именно чисел надо максимизировать?

[Tiberium]

thething в сообщении #1332865 писал(а):

одновременно я не понимаю. Также непонятен вопрос. Сумму каких именно чисел надо максимизировать?

My bad. Опечатался в условии.

[ex-math]

Про максимальное значение все равно непонятно. Матрица заполняется однозначно, что максимизировать-то?

[Tiberium]

ex-math в сообщении #1332871 писал(а):

Про максимальное значение все равно непонятно. Матрица заполняется однозначно, что максимизировать-то?

Я слепой осел, извините. Дважды перечитал, и все равно криво переписал.

[Someone]

Tiberium в сообщении #1332859 писал(а):

В этой матрице выбрано 2017 чисел так, что в каждой строке и каждом столбце выбрано ровно одно число.
Найдите максимальное значение, которое может принимать сумма этих чисел.

А разница есть, какие числа выбрать?

[ex-math]

Да, вроде как ни выбирай, одно и то же будет.

[Tiberium]

Someone
ex-math

Да, мне тоже это показалось странным. По идее, задача должна была быть сложнее.

[Someone]

Tiberium в сообщении #1332887 писал(а):

По идее, задача должна была быть сложнее.

Ну, надо же аккуратно доказать, что при любом выборе чисел получится одно и то же.

[DeBill]

А вот если бы таблица была - десять на десять, а числа начинались с 00, то явно видно все - ибо цифры в кажном из разрядов у выбранных чисел - хороши... И сумма считается.

[wrest]

DeBill в сообщении #1332956 писал(а):

А вот если бы таблица была - десять на десять, а числа начинались с 00,

Точно!

[Shadow]

(Оффтоп)

wrest в сообщении #1332958 писал(а):

Так в чем проблема

это не проблема, а подсказка. Пусть никнейм вас не подводит.

[mihaild]

(Оффтоп)

А какое обобщение? Если у матрицы $A$ все строки одинаковые, у $B$ все столбцы одинаковые, $C$ - дважды стохастическая, то $\operatorname{tr}((A+B)C) = \operatorname{tr}(A + B)$?