Последовательность натуральных чисел

[Профессор Снэйп]

Для последовательности натуральных чисел $\{ s_n \}_{n \in \mathbb{N}}$, в которой каждое натуральное число встречается хотя бы один раз, выполнено

\[ \frac{1}{2005} < \frac{|s_n-s_m|}{|n-m|} < 2005 \]

при всех натуральных $n \neq m$.

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

[Профессор Снэйп]

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

1) Доказать, что для всех натуральных $n$ выполнено $|s_n-n| \leqslant 2008008$.

2) Доказать, что при всех натуральных $n$ справедливо $|s_n-n| < 2007007$.

3) Улучшить оценку из предыдущего пункта.

P. S. Первые два пункта сам решать умею, третий нет. Хотя интуиция прямо таки вопит мне в уши, что оценку улучшить можно.

P. P. S. Для определённости пусть натуральный ряд начинается с единицы, хотя это совершенно не важно.

[nn910]

Откудато взялась негативная энергия оценивать все снизу.
Обозначим $2005=A$, тогда оценка снизу для максимального $s_n-n$ получается$\dfrac{(A-1)^2}{2}$ при нечетных A. Последовательность биективная, пытался изобразить ее график типа пилы вдоль и поперек, но LaTeX ,по Львовскому, не знает угловых коэффициентов больше 6, а у меня для A=7 он естессно 7.Вот она:
1,8,15,22,16,9,2,7,14,21,23,17,10,3,6,13,20,24,18,11,4,5,12,19,25 и с этого места по формуле $s_{n+24}=s_n+24$ Ну принцип понятен.Тогда при A=2005 получается 2008008 Профессор?

[TOTAL]

nn910 в сообщении #233261 писал(а):

Вот она:
1,8,15,22,16,9,2,7,14,21,23,17,10,3,6,13,20,24,18,11,4,5,12,19,25 и с этого места по формуле $s_{n+24}=s_n+24$ Ну принцип понятен.Тогда при m=2005 получается 2008008 Профессор?

при m=2005 разность не больше 25

[ewert]

nn910 в сообщении #233261 писал(а):

но LaTeX ,по Львовскому, не знает угловых коэффициентов больше 6,

Знает (гл.V, п.4): $\begin{picture}(40,40) \qbezier(0,0)(2,19)(4,38) \qbezier(4,38)(20,36.5)(36,35) \qbezier(36,35)(18,17.5)(0,0) \end{picture}$

[Профессор Снэйп]

nn910 в сообщении #233261 писал(а):

Профессор?

Что "профессор"? Я, если честно, не понял, что Вы написали.

Особенно вот этот момент:

nn910 в сообщении #233261 писал(а):

Вот она:
1,8,15,22,16,9,2,7,14,21,23,17,10,3,6,13,20,24,18,11,4,5,12,19,25 и с этого места по формуле $s_{n+24} = s_n + 24$.

Вообще-то последовательность никак не фиксирована, указаны только её свойства. Этим свойствам удовлетворяет множество последовательностей. В частности, Ваша последовательность, последовательность $1,2,3,\ldots$ и многие другие. И что? В задаче требуется доказать, что все они удовлетворяют определённому свойству. У Вас никаких доказательств не наблюдается!

TOTAL в сообщении #233276 писал(а):

при m=2005 разность не больше 25

И что? О какой разности речь? Не понял, к чему это?

P. S. При условии

$$ \frac{1}{A} < \frac{|s_n - s_m |}{|n-m|} < A $$

для $A \in \mathbb{N}$ оценка $|s_n - n| \leqslant (A-1)^2/2$, безусловно, имеет место (хотя, безусловно, нуждается в доказательстве, которого я пока нигде не увидел). При $A = 2005$ имеем $2004^2/2 = 2008008$, то есть первый пункт задачи. Возможно, при малых $A$ эта оценка точна, но при больших $A$ это не так! О чём, в частности, свидетельствует второй пункт задачи

P. P. S. Для дальнейших рассуждений замените у себя $m$ на какую-нибудь другую букву. Просто $m$ уже фигурирует в условии, может возникнуть путаница. Я предлагаю $A$.

[TOTAL]

Профессор Снэйп в сообщении #233283 писал(а):

И что? О какой разности речь? Не понял, к чему это?

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

[Профессор Снэйп]

TOTAL в сообщении #233288 писал(а):

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

Ок. Ясно, к чему Ваше замечание.

Я человека понял по другому. Он для $A = 7$ ($m=7$ в его обозначениях) приводит пример, когда оценка $(A-1)^2/2$ точна. Даже четвёртый член последовательности выделил жирным шрифтом для наглядности. Неясно, правда, зачем он всё это делает; в условии предлагалось решить задачу совсем для другого $A$.

Вообще, странный товарищ, и пишет довольно невнятно. Но вроде не альт

-- Чт авг 06, 2009 15:31:08 --

Даже не так! Вгляделся в его последовательность. У него $s_1 = 1$, $s_2 = 8$, так что при $n=1$ и $m=2$

$$ \frac{|s_n-s_m|}{|n-m|} = 7 < 8 $$

и последовательность эта для $A=8$, а не для $A=7$. Товарисч вообще полную бессмыслицу написал

[TOTAL]

nn910 в сообщении #233261 писал(а):

Ну принцип понятен.

Мне принцип непонятен. Объясните.

[nn910]

Профессор Снэйп в сообщении #233283 писал(а):

nn910 в сообщении #233261 писал(а):

Вот она:
1,8,15,22,16,9,2,7,14,21,23,17,10,3,6,13,20,24,18,11,4,5,12,19,25 и с этого места по формуле $s_{n+24} = s_n + 24$.

Вообще-то последовательность никак не фиксирована, указаны только её свойства. Этим свойствам удовлетворяет множество последовательностей. В частности, Ваша последовательность, последовательность $1,2,3,\ldots$ и многие другие. И что? В задаче требуется доказать, что все они удовлетворяют определённому свойству. У Вас никаких доказательств не наблюдается!

Я предлагаю $A$.

Виноват, сейчас исправлю все на А.
Я как раз и не уверен, что из трех утверждений Вашей задачи 2 последних вообще верны. Но мое рассуждение сырое, и если бы я описал его сразу в 5 раз подробнее, нарвался бы на в 25 раз больше вопросов, что Вы Профессор называете flood. Поэтому попробовал выразить идею построения контрпримера, но Вы неожиданно быстро ответили и не так как я ожидал. Ожидались 3 варианта:а)Вы указали бы, что контрпример не удовлетворяет условию задачи для А=7,б)Вы согласились бы,но потребовали обобщить на А=2005 (требует времени)в)Вы сообщили бы что берете паузу и стали бы подставлять в имеющиеся у Вас доказательства (думаю,непростые) вместо А=2005 А=7 и мою последовательность,чтобы понять где ошибка.
Поэтому пока просто повторю простое утверждение:
Существует биективная $s_n$ такая что $\dfrac{1}{7}\leq\dfrac{|s_n-s_m|}{|n-m|}\leq7$ для всех неравных m и n, но$s_4-4=18$Построение.Вот она:
1,8,15,22,16,9,2,7,14,21,23,17,10,3,6,13,20,24,18,11,4,5,12,19,25 и с этого места по формуле $s_{n+24} = s_n + 24$Первые 24 члена определены, по формуле находим через них кусок последовательности с 25-го по 48й,через этот кусок следующий, и тд.Выполнение правого неравенства достаточно проверить для n=m+1 и m=1...24 (В Excel), левого, в виде $\dfrac{|n-m|}{|s_n-s_m|}\leq7$-для таких же n,m только в Excel применить сортировку. Что обещал-доказал. Насчет обобщения на большие А. На поиск логики в последовательности VAL проводил тур марафона, сначала у них подучусь формулировать,чтоб сообщить Вам неубойно. Надеюсь не я один считаю что логика есть (нарисовать графики в Excel исходной и сортированной).
Профессор? (Вариантов
Вашего ответа у меня теперь больше 3,например такой :Вы намекаете что не желаете видеть в этом топике мою последовательность и меня - и нас не будет. Топиков много, времени мало.)

[Профессор Снэйп]

Пардон, nn910, Вы строгое неравенство от нестрогого отличаете?

В условии написано

$$ \frac{1}{A} < \frac{|s_n-s_m|}{|n-m|} < A, $$

а не

$$ \frac{1}{A} \leqslant \frac{|s_n-s_m|}{|n-m|} \leqslant A. $$

Если Вы хотите рассматривать нестрогое неравенство вместо строгого, то $A$ на единичку уменьшается. А Вы, перед тем как возводить в квадрат и делить пополам, тоже отнимаете единичку, уже от уменьшенного $A$. То есть от исходного $A$ Вы отнимаете двойку и приводите пример, когда достигается оценка $(A-2)^2/2$.

В самом деле, как я уже указывал выше, для той последовательности, которую Вы приводите в пример, справедливо

$$ \frac{1}{8} < \frac{|s_n-s_m|}{|n-m|} < 8, $$

то есть $A$ равно $8$, а не $7$, как Вы полагаете! У Вас же разность $18 = |s_4-4|$ --- это $6^2/2$, а не $7^2/2$. То есть у Вас даже намёком на какой-то контрпример не пахнет.

Разберитесь сначала с этой арифметикой

[nn910]

Профессор Снэйп в сообщении #91787 писал(а):

Для последовательности натуральных чисел $\{ s_n \}_{n \in \mathbb{N}}$, в которой каждое натуральное число встречается хотя бы один раз, выполнено

\[ \frac{1}{2005} < \frac{|s_n-s_m|}{|n-m|} < 2005 \]

при всех натуральных $n \neq m$.

Про то, что надо доказать, читайте в следующем сообщении :)

А я думал,тут нестрогое неравенство. Зачем было давать по пол-условия в двух постах. Ну тогда ,надо еще проверить, в задаче 3 нельзя получить лучше чем 2006005. А задачи 1 и 2 (возможно) верны. Но мне уже неважно.

[Профессор Снэйп]

nn910 в сообщении #233316 писал(а):

А я думал,тут нестрогое неравенство.

По моему, написано строгое. Как можно было подумать что-то другое?

И от того, что задача сформулирована в двух постах, строгое неравенство не становится нестрогим

Не, если не хотите, не решайте, никто не заставляет. Но в том, что Вы невнимательно прочитали условие, никто, кроме Вас самих, не виноват

-- Чт авг 06, 2009 16:55:15 --

nn910 в сообщении #233316 писал(а):

Ну тогда ,надо еще проверить, в задаче 3 нельзя получить лучше чем 2006005.

Возможно, это так и $|s_n-n| \leqslant 2006005$ --- точная оценка. Я умею доказывать лишь $|s_n-n| < 2007007$. Но пока что даже доказательство для $|s_n-n| \leqslant 2008008$ не было озвучено

[Профессор Снэйп]

Авторское решение первого пункта.

Пусть $A > 1$ --- целое число и $\{ s_n \}_{n \in \mathbb{N}}$ --- последовательность натуральных чисел, для которой

$$ \frac{1}{A} < \frac{|s_n - s_m|}{|n-m|} < A $$

при всех натуральных $n \neq m$, причём каждое натуральное число встречается в последовательности хотя бы один раз. Вместо $s_n$ будем писать $s(n)$.

1) Функция $s : \mathbb{N} \to \mathbb{N}$ сюрьективна по условию. Кроме того, из неравенства $|n-m|/A < |s(n)-s(m)|$ при $n \neq m$ получаем, что эта функция инъективна. Значит, $s$ --- перестановка натурального ряда.

2) Подставляя в условие $m=n+1$, имеем $|s(n+1) - s(n)| < A$. Но так как числа $A$ и $|s(n+1)-s(n)|$ целые, то $|s(n+1) - s(n)| \leqslant A-1$. Отсюда, используя индукцию по $|n-m|$, получаем $|s(n) - s(m)| \leqslant (A-1)|n-m|$ при всех натуральных $n$ и $m$.

3) Благодаря первому пункту можно рассматривать обратную функцию $s^{-1}$. Взяв числа $n' = s(n)$ и $m' = s(m)$, перепишем условие в виде

$$ \frac{1}{A} < \frac{|n'-m'|}{|s^{-1}(n')-s^{-1}(m')|} < A. $$

Это равносильно тому, что

$$ \frac{1}{A} < \frac{|s^{-1}(n')-s^{-1}(m')|}{|n'-m'|} < A $$

при всех $n' \neq m'$. Повторяя рассуждения второго пункта, получаем $|s^{-1}(n)-s^{-1}(m)| \leqslant (A-1)|n-m|$ для всех $n,m \in \mathbb{N}$.

4) Пусть $|s(n) - n| > (A-1)^2/2$ для некоторого $n$. Переходя при необходимости от $s$ к $s^{-1}$, можно считать, что $s(n) < n$. Имеем $s(n+1) \leqslant s(n) + (A-1) \leqslant s(n) + (A-1)^2/2 + 1/2 \leqslant n$. Значит, существует $m < n$, такое что $s(m) > n$, ибо в противном случае перестановка $s$ отображает отрезок $[1,n+1]$ в отрезок $[1,n]$. Выберем $m < n$ с максимально возможным значением $s(m)$. Пусть $k > n$ таково, что $s(k) = s(m)+1$. Имеем

$$ \frac{(A-1)^2}{2} < n - s(n) < s(m) - s(n) \leqslant (A-1)(n-m) $$

и $n-m > (A-1)/2$. Аналогично для $k$ получаем

$$ \frac{(A-1)^2}{2} < n - s(n) < s(k) - s(n) \leqslant (A-1)(k-n) $$

и $k-n > (A-1)/2$. Складывая полученные два неравенства, заключаем, что $k-m > A-1$. Однако $m = s^{-1}(s(m))$, $k = s^{-1}(s(m)+1)$, и по третьему пункту должно выполняться $k-m \leqslant A-1$. Противоречие.

5) Таким образом, мы доказали, что $|s(n) - n| \leqslant (A-1)^2/2$ при всех натуральных $n$. Остаётся лишь подставить $A = 2005$ в эту формулу

[Sonic86]

 У nn910 принцип построения последовательности примерно такой.

$A_1=A-1$. Тогда $\frac{1}{A}<\frac{|s(m)-s(n)|}{|m-n|}<A \Leftrightarrow \frac{1}{A_1} \leq \frac{|s(m)-s(n)|}{|m-n|} \leq A_1$

Делаем $\frac{A_1-1}{2}$ наибольших шагов вверх, чтобы разность $s(n)-n$ получилась $\sim \frac{A^2}{2}$, а затем продолжаем прыжки вверх-вниз, чтобы удовлетворить условию биективности $s(n)$ и $\frac{1}{A_1} \leq \frac{|s(m)-s(n)|}{|m-n|} \leq A_1$ (вообще правильно было написано - надо в Excel нарисовать, и тогда все очевидно будет, а точно ее описывать замучаешься, а понимать это описание - тем более).

Точное описание:

Пусть $A_1 \geq 5$ нечетно, $s(1)=1$. Далее строим $s(n)$ следующим образом.

В $s(n+1)=s(n)+d(n)$. Определим $d(n)$:

$1 \leq n \leq \frac{A_1-1}{2} \Rightarrow d(n)=+A_1$

$n = \frac{A_1+1}{2} \Rightarrow d(n)= - (A_1-1)$

.........................................

$n = -\frac{A_1-1}{2}+A_1k \Rightarrow d(n)= - (A_1-1)$

$1-\frac{A_1-1}{2}+A_1k \leq n \leq A_1k-1 \Rightarrow d(n)=-A_1$

$n = A_1k \Rightarrow d(n)= + (A_1-(2k-1))$

$1+A_1k \leq n \leq \frac{A_1-1}{2}+A_1k \Rightarrow d(n)=+A_1$

$n = 1+\frac{A_1-1}{2}+A_1k \Rightarrow d(n)= - (2k-1)$

$1 \leq k \leq \frac{A-1}{2}$

для остальных $n$ $s(n)=n$, для простоты.

Например, для $A=7,1 \leq n \leq 24$ $d(n)=7;7;7;-6;-7;-7;5;7;7;2;-6;-7;-7;3;7;7;4;-6;-7;-7;1-7;7;6$. Всего $\frac{A_1^2-1}{2}$ членов.



Последовательность строится по следующему принципу: каждый следующий член берется таким, чтобы не нарушалась инъективность $s(n)$ и свойство $\frac{1}{A_1} \leq \frac{|s(m)-s(n)|}{|m-n|} \leq A_1$, и в целом - чтобы выполнялось требование сюръективности.

Из того, что $|d(n)| \leq A_1$ по индукции следует, что $\frac{|s(m)-s(n)|}{|m-n|} \leq A_1$.

Далее, при построении для каждого $s(n)$ и для $s(r)=s(n) \pm 1$ $|r-n| \leq A_1$, откуда по индукции получаем $\frac{|m-n|}{|s(m)-s(n)|} \geq A_1$. (могу инъективность и этот пункт расписать, если нужно, просто долго описывать, сложно)

$s(n)$ инъективна по построению, а поскольку при $1 \leq n \leq \frac{A_1^2-1}{2}$ $1 \leq s(n) \leq \frac{A_1^2-1}{2}$, то $s(n)$ будет сюръективна.

Таким образом, существует $s(n): \max\limits_{n} \{ |s(n)-n|\} = \frac{(A_1-1)(A_1-1)}{2} \sim \frac{A_1^2}{2}$. Значит вообще, если для $s(n):\frac{1}{A}<\frac{|s(m)-s(n)|}{|m-n|}<A \Rightarrow \max \{ s(n)-n \} \leq B(A)$, то $\frac{(A-3)^2}{2} \leq B(A) \leq \frac{(A-1)^2}{2}$. (если $A_1$ нечетно, то нижняя граница равна $\frac{(A-2)^2}{2}$, если же $A_1$ четно, то мы можем взять пример для $A_1-1$, для которого оценка снизу равна $\frac{(A-3)^2}{2}$).

Ну все равно $B(A) \sim \frac{A^2}{2}$, лучше уже не получится.