Здравствуйте, fAX, Вы писали:

fAX>Здравствуйте, Chorkov, Вы писали:

fAX>На самом деле всё гораздо проще:
fAX>Возьмём максимальное число. На сколько от него может уйти минимальное? Да не больше, чем на N (из условия связности)!!! По принципу "голубятни" — Есть как минимум одно число которое содержится N или более раз. (Если меньше, то сумма всех чисел меньше N^2)

0 1 2
1 2 3
2 3 4

4-0 = 4 > 3

Здравствуйте, MichaelP, Вы писали:

MP>4-0 = 4 > 3

Да уж...
Думаю, со второго раза будет лучше...

Здравствуйте, UgN, Вы писали:

fAX>Я прекрасно понимаю, что Вы имели в виду. Проблема как раз в "нахлёсте". Вы считаете числа в различных позициях различное число раз.

UgN>Так а при чем тут нечетная сторона квадрата?
А дело вот в чём: ответ к задаче, которую я привёл выше — да, может. А дело как раз в том, что 12 не делится на 5 — те же "нахлёсты" (В любых 5 последовательных месяцах — одно; в целом — другое). В той задаче нельзя экстраполировать результат. Это меня и смущает.

fAX.

Здравствуйте, fAX, Вы писали:

fAX>На самом деле всё гораздо проще:
fAX>Возьмём максимальное число. На сколько от него может уйти минимальное? Да не больше, чем на N (из условия связности)!!! По принципу "голубятни" — Есть как минимум одно число которое содержится N или более раз. (Если меньше, то количество всех чисел меньше N^2)

Ты хотел сказать — на 2N-2? Если максимум — в одном углу, а минимум — в противоположном. Равномерный градиент по диагонали.

 0   1   2  ...  N-1
 1   2   3  ...  N
 2   3   4  ...  N+1
....................
N-1  N  N+1 ... 2N-1

Пусть каждое число повторено N-1 раз. Разных чисел 2N-1. Итого количество равно 2N^2-3N+1.

В общем, фокус с оценкой не удался. (Хотя, конечно, сама картинка говорит, что вот же повторяемое число, N-1, на поперечной диагонали).