Целочисленные последовательности

[arseniiv]

(Здесь $\mathbb N$ имеется в виду с нулём.)

Для данной последовательности $a\colon \mathbb N \to\mathbb N$ определим множество вхождений данного элемента $D(n) := \{i : a_i = n\}$.
Ещё, пусть $M + n := \{m + n : m\in M\}$.

Найдите все такие последовательности, что $\forall n\in\mathbb N \mathbin. \exists s\in\mathbb N \mathbin. D(n) = D(0) + s$.

[Руст]

arseniiv в сообщении #680015 писал(а):

(Здесь $\mathbb N$ имеется в виду с нулём.)

Для данной последовательности $a\colon \mathbb N \to\mathbb N$ определим множество вхождений данного элемента $D(n) := \{i : a_i = n\}$.
Ещё, пусть $M + n := \{m + n : m\in M\}$.

Найдите все такие последовательности, что $\forall n\in\mathbb N \mathbin. \exists s\in\mathbb N \mathbin. D(n) = D(0) + s$.

Несколько неточностей. Обычно множество, удовлетворяющее некоторому свойству пишется через черту: $D(n) := \{i | a_i = n\}$.
В русской литературе обычно $0\not \in N$.
Сама задача очевидная (считаем, что $0\in N$). Ваше условие эквивалентно тому, что последовательность есть биекция и $a_0=0$.

[0_menge]

Руст в сообщении #680080 писал(а):

Ваше условие эквивалентно тому, что последовательность есть биекция и $a_0=0$.

Странно, но $a_n=[n/2]$ удовлетворяет условию, но биекцией не является. Поправьте, если ошибся.

Кажется, даже $a_n=[n/k]$ для любого целого положительного $k$ и их перестановки определенного вида (меняем местами сразу $k$ подряд идущих одинаковых членов) удовлетворяют условию. Скорее всего это и есть ответ, но я не знаю как это доказать.

[Cash]

Этих последовательностей гораздо больше. $a_0=0$, а дальше... Непонятно только зачем предъявлять последовательности, достаточно ведь указать все допустимые $D(0)$. Например, подходит $\{0, k \}$. С конечными $D(0)$ вроде все просто, самое интересное, когда $D(0)$ бесконечно и может ли оно такое быть?

[Руст]

Да, случаи не одноэлементных $D(0)$ возможны (я поторопился).
По сути, условие означает, что множество $D(0)$ и бесконечная серия ее сдвигов $D(n)=D(0)+s(n)$ взаимно однозначно покрывают неотрицательные целые числа.
Вообще то в условии не сказано, что сложение определено только для натуральных $D(n)=D(0)+s(n),$ с $s(n)\ge 0$. Соответственно $a_0=0$ не обязательно. Любые перестановки $\phi:N\to N$ возможны, при этом $a_n\to a_{\phi(n)}$.
Соответственно, задача сводится к классификации возможных множеств $D(0)$, сдвиги которых покрывают натуральный ряд (с 0).
Таких множеств много, даже с бесконечным числом элементов.
Например: пусть $D(0)$ состоит из всех чисел в p- ичной системе исчисления $D(0)=\{a_k+p^k, a_i=0,...,p-1, k=0,2,4,6,...\}$.

[Cash]

Руст в сообщении #680150 писал(а):

Вообще то в условии не сказано, что сложение определено только для натуральных $D(n)=D(0)+s(n),$ с $s(n)\ge 0$. Соответственно $a_0=0$ не обязательно.

Вообще-то, сказано (хотя, согласен, это и не принципиально).

Цитата:

$\forall n\in\mathbb N \mathbin. \exists s\in\mathbb N \mathbin. D(n) = D(0) + s$

[arseniiv]

Cash в сообщении #680140 писал(а):

Непонятно только зачем предъявлять последовательности, достаточно ведь указать все допустимые $D(0)$.

Да, надо было, и правда, так сформулировать.

Кстати, меня больше интересуют именно бесконечные $D(0)$, при которых последовательность сюръективна [пока писал условие, пытался вспомнить, ничего ли не забыл, но, как теперь видно, это не помогло]. Сам нашёл одну серию $D(0) = \left\{k\sum A : A\subset\{1,4,4^2,4^3,\ldots\} \wedge |A|\in\mathbb N \right\}$.

А вот легко ли перечислить все бесконечные $D(0)$, дающие сюръективную последовательность?.. (Если их вдруг несчётное число, то я, конечно, не прошу. )

(Обозначения и пр.)

Руст в сообщении #680080 писал(а):

В русской литературе обычно $0\not \in N$.

Так потому и поместил соответствующее примечание в самой первой строке. В самом деле, писать всё время вместо этого что-то длиннее было бы неудобно — вхождений $\mathbb N$ в условии достаточно.

Руст в сообщении #680080 писал(а):

Несколько неточностей. Обычно множество, удовлетворяющее некоторому свойству пишется через черту: $D(n) := \{i | a_i = n\}$.

Угу, про вариант обозначения $\{ x \mid \phi\}$ знаю.

[Руст]

arseniiv в сообщении #680261 писал(а):

(Если их вдруг несчётное число, то я, конечно, не прошу. )

Их несчетное множество. Можно взять в качестве $D(0)=\{0, n_1,n_2,...\}$, где $n_1=m_1, n_i=n_{i-1}*m_i$ с произвольной последовательностью натуральных чисел $m_i\ge 2$, а их несчетное количество.

[arseniiv]

Не получается для $m_i = 2$ ($D(0) = \{0,2,4,8,16,\ldots\}$) — 0 размещается, 1 размещается, а 2 не влезает.

[Руст]

arseniiv в сообщении #680414 писал(а):

Не получается для $m_i = 2$ ($D(0) = \{0,2,4,8,16,\ldots\}$) — 0 размещается, 1 размещается, а 2 не влезает.

Я нечетко выразился. Расстояния должны расти. Здесь $(0,2,4)$ одинаковые расстояния.
Для гарантированности можно брать $2\le m_1<m_2<m_3<...$ (все равно таких последовательностей континиум).

[Ktina]

arseniiv в сообщении #680015 писал(а):

(Здесь $\mathbb N$ имеется в виду с нулём.)

Тогда это уже не $\mathbb N$, а $\mathbb N_0$

[Руст]

Для задачи это не принципиально. Чтобы не раздражать русскую школу, можно было задать $D(1)$ вместо $D(0)$ в условии.

[arseniiv]

Не совсем, ноль используется ещё в значении $s$, чтобы формула $\exists s\in\mathbb N \mathbin. D(0) = D(0) + s$ была верна.

Руст в сообщении #680504 писал(а):

Я нечетко выразился. Расстояния должны расти. Здесь $(0,2,4)$ одинаковые расстояния.
Для гарантированности можно брать $2\le m_1<m_2<m_3<...$ (все равно таких последовательностей континиум).

Спасибо.

(Оффтоп)

Кстати, я ерунду написал в

arseniiv в сообщении #680261 писал(а):

Кстати, меня больше интересуют именно бесконечные $D(0)$, при которых последовательность сюръективна [пока писал условие, пытался вспомнить, ничего ли не забыл, но, как теперь видно, это не помогло].

т. к. условие и так требует сюръективности. А вот бесконечность $D(0)$, правда, была упущена.

[Руст]

arseniiv в сообщении #680612 писал(а):

Спасибо.

Не за что. Только я опять был не точен. Чтобы действительно быть точным лучше было бы исключить 0. Достаточно в условии заменить 0 на 1. Соответственно я решу в таком случае.

1. Объединяем первые подряд идущие числа $1,...,k$ в один пакет. Тогда все пропуски должны делиться на это число. И вообще отображение $i\to a_i$ пропускается через $i\to[\frac{i-1}{k}]+1$. Соответственно задачу свели к случаю (пропуская через это отбражение) к случаю, когда $k=1$ (на 1 всегда имеется делимость).
2. Пусть следующим элементом в $D(1)=\{1,n_1,n_2,...\}$ будет $n_1>2$. Первый пробел имееи длину $k_1=n_1-n_0=n_1-1$.
Тогда $D(1),D(1)+1,...D(1)+n_1-2$ закрывает этот пробел и нет другого способа закрытия этого пробела.
Соответственно будут покрыты числа как минимум до $2n_1-2$ включительно. Если $n_2}=2n_1-1$, то будут покрыты до $3n_1-3=n_2+n_1-2$ включительно и если $n_j=1+j(n_1-1), 1\le j< m_1$, то до $m_1(n_1-1)$. Тогда, если еще не исчерпали все элементы из $d(1)$, то длины всех пробелов должны делиться на это число $k_2=m_1*k_1$.
3. Далее переходим к следующему уровню пропуская через отображение $i\to [\frac{i-1}{k_2}]+1$. Получаем с конечным или бесконечным уровнем фрактальное решение.