Задача с натуральным рядом

[Rusit8800]

Задача 1:Найти максимальное натуральное число $A$ такое, что при любой расстановке всех натуральных чисел от $1$ до $100$ включительно в ряд в некотором порядке всегда найдутся десять последовательно расположенных чисел, сумма которых не меньше $A$.

Эту задачу я решил сразу обобщить, чтобы попробовать прийти к решению изначальной задачи из неких общих соображений:
Задача 2: Найти максимальное натуральное число $A$ такое, что при любой расстановке всех натуральных чисел от $1$ до $n$ включительно в ряд в некотором порядке всегда найдутся $k$ последовательно расположенных чисел, сумма которых не меньше $A$.

Решить ни ту, ни другую задачу у меня не удалось, однако у меня есть некие соображения по поводу общей задачи. Надеюсь, что форумчане либо разовьют мою идею, либо предложат другую хотя бы для частной задачи.



Пусть $\[{\Pi _i}\]$ - $i$-ая перестановка $n$ чисел, причем $\[1 \leqslant i \leqslant n!\]$. Определим $\[\left\{ {{a_1},{a_2},...,{a_{A_n^k}}} \right\}\]$ как множество всех расстановок без повторений чисел $1,2,...,n$ по $k$ местам, а числа $\[{{s_1},{s_2},...,{s_{A_n^k}}}\]$ как суммы чисел в соответствующих расстановках. Далее, рассмотрим последовательность $\[{\Pi _i}\]$:

$$\[{\Pi _i}:{\text{ }}\underbrace {{t_1}{\text{ }}{t_2}{\text{ }}{t_3}{\text{ }} \ldots {\text{ }}{t_k}}_{{a_j}}{\text{ }}{t_{k + 1}}{\text{ }}{t_{k + 2}}{\text{ }} \ldots {\text{ }}\underbrace {{t_{n - k + 1}}{\text{ }} \ldots {\text{ }}{t_{n - 1}}{\text{ }}{t_n}}_{{a_{j + (n - k)}}}\]$$

Как видно из схемы, данная последовательность определяется $n-k+1$ элементами из $\[\left\{ {{a_1},{a_2},...,{a_{A_n^k}}} \right\}\]$, а именно $\[{a_j},{a_{j + 1}}, \ldots ,{a_{j + (n - k)}}\]$. Два элемента $a_u$ и $a_{u+1}$ отличаются друг от друга только одним числом - последовательность чисел, задаваемая $a_{u+1}$, сдвинута вправо относительно последовательности чисел, которую задает расстановка $a_{u}$ (последовательности чисел $a_{u}$ и $a_{u+1}$, можно сказать, являются соседними). Числа $t_1,t_2,...t_n$ представляют с собой переставленные числа $1,2,...,n$. Пусть еще $A_j=\[\max \left( {{s_j},{s_{j + 1}}, \ldots ,{s_{j + (n - k)}}} \right)\]$.
Покажем, что $\[A = \min \left( {{A_1},{A_2}, \ldots ,{A_{n!}}} \right)\]$. Действительно, условие задачи равносильно тому, чтобы для числа $A$ выполнялись неравенства $\[A \leqslant {A_j}\]$ для всех $j$. Если $v=\min \left( {{A_1},{A_2}, \ldots ,{A_{n!}}} \right)$, то предыдущая система неравенств равносильна $A \leqslant v$. Но поскольку наша цель - максимизировать число $A$, то остается положить $A=v$. Мы, таким образом, свели задачу к поиску числа $\[\min \left( {{A_1},{A_2}, \ldots ,{A_{n!}}} \right)\]$.
Мои продвижения следующие:
1)

$$\[\max \left( {{A_1},{A_2}, \ldots ,{A_{n!}}} \right) = \left( {n - k + 1} \right) + \left( {n - k + 2} \right) + \ldots + \left( {n - 1} \right) + n\]$$

Действительно, в некоторой последовательности $\[{\Pi _i}\]$ найдется кортеж $a_h=\[\left\langle {\left( {n - k + 1} \right),\left( {n - k + 2} \right), \ldots ,\left( {n - 1} \right),n} \right\rangle \]$, сумма $s_h$ которого, очевидно, максимальна среди всех сумм $\[{s_1},{s_2},...,{s_{A_n^k}$.
2)

$$\[A \geqslant \sum\limits_{i = 1}^k i \]$$

Это следствие того, что величина $\[\sum\limits_{i = 1}^k i \]$ меньше или равна числам ${s_1},{s_2},...,{s_{A_n^k}$

[B@R5uk]

Я не особо вникал в условие, но разве максимально возможное значение величины $A$ не будет связано со средним значением чисел вашего исходного множества? Ну, с небольшими поправками на краевые эффекты.

[Rusit8800]

B@R5uk в сообщении #1363888 писал(а):

Я не особо вникал в условие, но разве максимально возможное значение величины $A$ не будет связано со средним значением чисел вашего исходного множества?

Как интересно - ваше предположение совпало с моей гипотезой, которую я не смог доказать и на форум решил не выкладывать! Но раз уж пошла такая пьянка, то давайте я ее тоже выложу.

"Продвижение" 3) Определим среднее значение сумм $\[{{s}_{\text{ср}}}\]$ следующим образом:

$$ \[{s_{{\text{ср}}}} = \frac{{\sum\limits_{i = 1}^{A_n^k} {{s_i}} }}{{A_n^k}}\] $$

Моя гипотеза состоит в том, что

$$\[\left\lfloor {{s_{{\text{ср}}}}} \right\rfloor = A\]$$

Она бы позволила свести вычисление $A$ к вычислению $\[{{s}_{\text{ср}}}\]$. Здесь возникают две трудности:
1) Гипотеза никак не поддается доказательству.
2) Вычисление $\[{{s}_{\text{ср}}}\]$ затруднительно даже для частной задачи, где $n=100$, $k=10$.
На этом мои продвижения и закончились.

[worm2]

Ну зачем же сразу $n=100$, $k=10$? Начните с малого: n=1-4, k=1-3 (сам в задачу тоже пока не вникал).

[Rusit8800]

B@R5uk в сообщении #1363888 писал(а):

Я не особо вникал в условие

worm2 в сообщении #1363914 писал(а):

сам в задачу тоже пока не вникал

Ну что ж такое то

-- 26.12.2018, 23:17 --

worm2 в сообщении #1363914 писал(а):

Ну зачем же сразу $n=100$, $k=10$?

Потому что это изначальная задача, которая привела к общей.
И опять же, вычисление $\[{{s}_{\text{ср}}}\]$ не имеет смысла, покуда не будет доказана гипотеза.

[Rusit8800]

(Оффтоп)

А будет ли законно размещать эту задачу в разделе олимпиад? Решения у меня, конечно, пока нет, но задача интересная, и может заинтересовать решателей олимпиад.

[worm2]

Задаче, разумеется, самое место в олимпиадном разделе. Можете попросить модераторов перенести (пожаловаться на своё сообщение кнопкой "!" и выбрать в поле "Причина" причину "размещена в несоответствующем разделе", а в пояснении написать, куда просите перенести).

Rusit8800 в сообщении #1363912 писал(а):

2) Вычисление $\[{{s}_{\text{ср}}}\]$ затруднительно

В силу симметрии это сделать довольно просто. Поскольку все значения абсолютно равнозначны, $s_\text{ср}$ будет равно среднему значению ($(n+1)/2$), умноженному на число слагаемых ($k$), т.е. $k(n+1)/2$

Цитата:

1) Гипотеза никак не поддается доказательству.

Видимо, потому что она неверна
Например, для $n=6$, $k=3$ значение $A$, вычисленное мною вручную, равно 11. А гипотеза даёт 10. Кроме того, гипотеза не учитывает краевые эффекты, о которых писал B@R5uk.

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

[Rusit8800]

worm2 в сообщении #1364027 писал(а):

Поскольку все значения абсолютно равнозначны, $s_\text{ср}$ будет равно среднему значению ($(n+1)/2$), умноженному на число слагаемых ($k$), т.е. $k(n+1)/2$

В принципе понятно, но, поскольку это неочевидно для меня, то как доказательство я это принять не могу.

worm2 в сообщении #1364027 писал(а):

Кроме того, гипотеза не учитывает краевые эффекты, о которых писал B@R5uk.

Это какие краевые эффекты? Мне на ум приходит только краевые эффекты электрического поля на границе плоского конденсатора.

[grizzly]

Мне кажется, всё просто. Среднее для (100;10) -- 505. Не меньше 505 среди каких-нибудь 10 рядом стоящих найдутся всегда (это и есть основной вопрос задачи, который нужно доказать). Остаётся ещё привести простой пример, когда ровно 505 достигается:
100; 1; 100-2, 1+2; 100-4; 1+4; ... ; 100-98, 1+98.

Краевых эффектов не возникло :)

[Rusit8800]

Такое чувство, что гипотеза дает несколько заниженное значение $A$. Вот например пример с $n=100,k=10$

$$\[(50{\text{ }}\underbrace {99{\text{ }}[1{\text{ }}98{\text{ }}2{\text{ }}97{\text{ }}3{\text{ }}96{\text{ }}4{\text{ }}95){\text{ }}5}_{500}{\text{ }}94]{\text{ }}6{\text{ }}93{\text{ }}7 \ldots 56{\text{ }}[44{\text{ }}\underbrace {55{\text{ }}(45{\text{ }}54{\text{ }}46{\text{ }}53{\text{ }}47{\text{ }}52{\text{ }}48{\text{ }}51]{\text{ }}49}_{500}{\text{ }}100)\]$$

Последовательности, помеченные фигурными скобками, имеют сумму чисел $500$, квадратными - $495$, круглыми - $545$, других значений нет, значит $\[A \leqslant 545\]$. Уменьшить число $545$ не удается.

[wrest]

Rusit8800 в сообщении #1363877 писал(а):

что при любой расстановке всех натуральных чисел от $1$ до $n$ включительно в ряд в некотором порядке всегда найдутся

Прошу прощения, а что значит "при любой расстановке в некотором порядке"?
Можно это как-то привести к "стандартным" терминам -- перестановкам?

[Rusit8800]

grizzly в сообщении #1364046 писал(а):

Не меньше 505 среди каких-нибудь 10 рядом стоящих найдутся всегда (это и есть основной вопрос задачи, который нужно доказать).

Хорошо, а почему меньше нельзя? Основной вопрос свелся к тому, чтобы найти минимальное из значений $A_j$, так что если можно подобрать последовательность, где максимальная сумма $10$ чисел будет меньше $505$, то $505$ уже не может быть ответом к задаче, так как ваша последовательность перестанет удовлетворять условиям задачи (обратите внимание на слово "любой", относящееся к перестановкам натуральных чисел).
Если бы можно было ослабить гипотезу хотя бы до $\[\left\lfloor {{s_{{\text{ср}}}}} \right\rfloor \leqslant A,\left\lceil {{s_{{\text{ср}}}}} \right\rceil \leqslant A\]$, то вопросов бы не было, ибо

$$\[\left\lfloor {\frac{{10(100 + 1)}}{2}} \right\rfloor = \left\lceil {\frac{{10(100 + 1)}}{2}} \right\rceil = 505\]$$

-- 27.12.2018, 14:08 --

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

Можно это как-то привести к "стандартным" терминам -- перестановкам?

Да, можно. Именно поэтому переменная $i$ ограничена сверху числом $n!$.

[wrest]

Rusit8800 в сообщении #1364052 писал(а):

Именно поэтому переменная $i$ ограничена сверху числом $n!$.

Ну ессно, ведь перестановок из $n$ элементов всего $n!$, но это не отвечает на мой вопрос о непонятном условии задачи.

[Rusit8800]

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

Ну ессно, ведь перестановок из $n$ элементов всего $n!$, но это не отвечает на мой вопрос о непонятном условии задачи.

Да, есть такое

[wrest]

Rusit8800
Тогда сформулируйте условие задачи же уже.
Вот у нас есть все перестановки из $n$ элементов, мы их пронумеровали, и их $n!$
И что дальше? В каждой перестановке найдется подпоследовательность длиной 10 такая, что...
Или что?