Последовательность

[daogiauvang]

Пусть последовательность$a_1,a_2,\cdots$ быть неубывающей натуральных чисел, удовлетворяющих $a_{a_k}=3k$ при любом $k$. Определить множество всех возможных значений $a_{2010}$.

[cyb12]

Обозначим $a_{2010}=t$. Последовательность неубывающая должна быть. Тогда рассмотрим $a_t=3\cdot 2010$.
Если $t>2010$, то $a_t\geqslant a_{2010}$, что то же самое, что и $3\cdot 2010\geqslant t$.
Если же $t<2010,$ то $a_t \leqslant a_{2010}$, то есть $3\cdot 2010 \leqslant t$.
Таким образом, $t\in[2010,3\cdot 2010]$.

Дальше пока не получается...
Проблема в том, что если $a_i=j$, то $a_j=3i$ и $a_{3i}=3j$. Но обратное не верно...

[daogiauvang]

$a_{2010}=a_{a_a_{670}}=3a_{670}$ Поэтому множество всех возможных значений $a_{2010} $ равно множеству всех возможных значений $a_{670}$

[koky]

Хм.. А что если$a_1 = 2011$ , тогда $a_{2010}$ не подподает под условие и может быть любым. Стоп, но тогда $a_1=2011, a_{2011}=3$ и она убывающая. Да, кстати при $a_1 >3 $ она не может считатся не убывающей.

[daogiauvang]

Легко доказали что, $a_1=1,a_2=2,a_3=3$. Я это уже получил.

[Xaositect]

daogiauvang в сообщении #334205 писал(а):

Легко доказали что, $a_1=1,a_2=2,a_3=3$. Я это уже получил.

Как раз наоборот, $a_k\neq k$, т.к. иначе $a_k = a_{a_k} = 3k \neq k$.

-- Ср июн 23, 2010 17:13:11 --

Соответственно, учитывая, что $a_1 > 3$ противоречит неубыванию, остаются два варианта для $a_1$

-- Ср июн 23, 2010 17:23:13 --

И для этих двух вариантов можно получить значения $a_{3^k}$, они лучше ограничивают, чем $[2010, 3\cdot 2010]$

Еще наша последовательность на самом деле строго возрастающая, т.к. $a_k = a_{k+1} = t\Rightarrow a_{t} = 3k = 3(k+1)$, чего быть не может.

-- Ср июн 23, 2010 17:36:24 --

В случае $a_1 = 2$ последовательность вообще однозначно определена, а случай $a_1 = 3$ невозможен. Подоказывайте сами, я уже и так много написал.

[koky]

А что если взять при $n<2010$, $a_{n}=3$, затем $a_{2010}$ взять любым числом из $[2010,3\cdot 2010]$. Вот, например:
$a_{2010}=2015, a_{2015}=2010\cdot3, a_{2010\cdot3}=2015\cdot3, a_{2015\cdot3}=2010\cdot{3^2}...$
Нужно, чтобы соблюдалось условие: $(2010+k)\cdot{3^n}<=2010\cdot{3^{n+1}}$, а это всё равно что$k<=2\cdot2010$,значит любое число из интервала $[2010,3\cdot 2010]$ подходит, а другие нет, для любой последовательности.

[Xaositect]

koky в сообщении #334220 писал(а):

А что если взять при $n<2010$, $a_{n}=3$, затем $a_{2010}$ взять любым числом из $[2010,3\cdot 2010]$. Вот, например:
$a_{2010}=2015, a_{2015}=2010\cdot3, a_{2010\cdot3}=2015\cdot3, a_{2015\cdot3}=2010\cdot{3^2}...$
Нужно, чтобы соблюдалось условие: $(2010+k)\cdot{3^n}<=2010\cdot{3^{n+1}}$, а это всё равно что$k<=2\cdot2010$,значит любое число из интервала $[2010,3\cdot 2010]$ подходит, а другие нет, для любой последовательности.

Xaositect в сообщении #334213 писал(а):

Еще наша последовательность на самом деле строго возрастающая, т.к. $a_k = a_{k+1} = t\Rightarrow a_{t} = 3k = 3(k+1)$, чего быть не может.

[koky]

Да, точно. Однако однозначность в случае $a_1=2$ не очевидна. А вот из срогого возрастания следует, что $a_{a_k}-a_k \ge a_k-k$

[cyb12]

Если $a_1=2,$ тогда получаем, что $a_2=3,$ $a_3=6.$
Тогда $a_6=9.$ Остаются $a_4$ и $a_5,$ которые, в силу строгого возрастания, берем 7 и 8 соответственно. Потому $a_7=12,$ $a_8=15,$ $a_9=18,$ $a_{12}=21,$ потому $a_{10}=19,$ $a_{11}=20.$ Но, да, не очевидно, что так будет дальше...

[Xaositect]

Ну, такие вещи по индукции доказываются.

[cyb12]

Хотя.
Если $a_k+1=a_{k+1},$ то два подряд идущих элемента $a_{a_k}$ и $a_{a_{k+1}}$ мы определяем однозначно. При этом $a_{a_k}=3k,$ а $a_{a_{k+1}}=3k+3$, то есть если $a_k+1\neq a_{k+1},$ то это означает, что между $a_{a_k}$ и $a_{a_{k+1}}$ мы можем вставить только 2 числа - $3k+1$ и $3k+2.$ То есть $a_{k+1} - a_k = 3.$
То бишь получается, что было бы все замечательно, если либо $a_{k+1} - a_k = 1,$ либо $a_{k+1} - a_k = 3$ ? Вот это можно доказать по индукции...

[koky]

мм..так вот.. из$a_{a_k}-a_k \ge a_k-k$ при $a_{a_k}=3k$ следует, что $2k\ge a_k$
значит $a_1\le2, a_2\le4 $