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
816
приходит весна?
Я не особо вникал в условие, но разве максимально возможное значение величины $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
2529
Уфа
Ну зачем же сразу $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
2529
Уфа
Задаче, разумеется, самое место в олимпиадном разделе. Можете попросить модераторов перенести (пожаловаться на своё сообщение кнопкой "!" и выбрать в поле "Причина" причину "размещена в несоответствующем разделе", а в пояснении написать, куда просите перенести).

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
6089
Мне кажется, всё просто. Среднее для (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
5599
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
5599
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
5599
Rusit8800
Тогда сформулируйте условие задачи же уже.
Вот у нас есть все перестановки из $n$ элементов, мы их пронумеровали, и их $n!$
И что дальше? В каждой перестановке найдется подпоследовательность длиной 10 такая, что...
Или что? :D

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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