2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3, 4  След.
 
 Задача с натуральным рядом
Сообщение26.12.2018, 20:44 
Аватара пользователя


15/11/15
1254
Москва
Задача 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}$

 Профиль  
                  
 
 Re: Задача с натуральным рядом
Сообщение26.12.2018, 21:30 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача с натуральным рядом
Сообщение26.12.2018, 23:08 
Аватара пользователя


15/11/15
1254
Москва
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$.
На этом мои продвижения и закончились.

 Профиль  
                  
 
 Re: Задача с натуральным рядом
Сообщение26.12.2018, 23:11 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача с натуральным рядом
Сообщение26.12.2018, 23:16 
Аватара пользователя


15/11/15
1254
Москва
B@R5uk в сообщении #1363888 писал(а):
Я не особо вникал в условие

worm2 в сообщении #1363914 писал(а):
сам в задачу тоже пока не вникал

Ну что ж такое то :-(

-- 26.12.2018, 23:17 --

worm2 в сообщении #1363914 писал(а):
Ну зачем же сразу $n=100$, $k=10$?

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

 Профиль  
                  
 
 Re: Задача с натуральным рядом
Сообщение27.12.2018, 10:26 
Аватара пользователя


15/11/15
1254
Москва

(Оффтоп)

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

 Профиль  
                  
 
 Re: Задача с натуральным рядом
Сообщение27.12.2018, 13:05 
Заслуженный участник
Аватара пользователя


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

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

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

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

 Профиль  
                  
 
 Re: Задача с натуральным рядом
Сообщение27.12.2018, 13:35 
Аватара пользователя


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

В принципе понятно, но, поскольку это неочевидно для меня, то как доказательство я это принять не могу.
worm2 в сообщении #1364027 писал(а):
Кроме того, гипотеза не учитывает краевые эффекты, о которых писал B@R5uk.

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

 Профиль  
                  
 
 Re: Задача с натуральным рядом
Сообщение27.12.2018, 13:51 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Задача с натуральным рядом
Сообщение27.12.2018, 13:59 
Аватара пользователя


15/11/15
1254
Москва
Такое чувство, что гипотеза дает несколько заниженное значение $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$ не удается.

 Профиль  
                  
 
 Re: Задача с натуральным рядом
Сообщение27.12.2018, 14:03 


05/09/16
6470
Rusit8800 в сообщении #1363877 писал(а):
что при любой расстановке всех натуральных чисел от $1$ до $n$ включительно в ряд в некотором порядке всегда найдутся

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

 Профиль  
                  
 
 Re: Задача с натуральным рядом
Сообщение27.12.2018, 14:07 
Аватара пользователя


15/11/15
1254
Москва
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!$.

 Профиль  
                  
 
 Re: Задача с натуральным рядом
Сообщение27.12.2018, 14:18 


05/09/16
6470
Rusit8800 в сообщении #1364052 писал(а):
Именно поэтому переменная $i$ ограничена сверху числом $n!$.

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

 Профиль  
                  
 
 Re: Задача с натуральным рядом
Сообщение27.12.2018, 14:20 
Аватара пользователя


15/11/15
1254
Москва
wrest в сообщении #1364056 писал(а):
Ну ессно, ведь перестановок из $n$ элементов всего $n!$, но это не отвечает на мой вопрос о непонятном условии задачи.

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

 Профиль  
                  
 
 Re: Задача с натуральным рядом
Сообщение27.12.2018, 14:25 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 49 ]  На страницу 1, 2, 3, 4  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Andrey A


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group