2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Целочисленные последовательности
Сообщение04.02.2013, 19:49 
Заслуженный участник


27/04/09
28128
(Здесь $\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$.

 Профиль  
                  
 
 Re: Целочисленные последовательности
Сообщение04.02.2013, 22:47 
Заслуженный участник


09/02/06
4397
Москва
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$.

 Профиль  
                  
 
 Re: Целочисленные последовательности
Сообщение04.02.2013, 23:56 


18/01/13
4
Руст в сообщении #680080 писал(а):
Ваше условие эквивалентно тому, что последовательность есть биекция и $a_0=0$.

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

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

 Профиль  
                  
 
 Re: Целочисленные последовательности
Сообщение05.02.2013, 07:04 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Целочисленные последовательности
Сообщение05.02.2013, 08:47 
Заслуженный участник


09/02/06
4397
Москва
Да, случаи не одноэлементных $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,...\}$.

 Профиль  
                  
 
 Re: Целочисленные последовательности
Сообщение05.02.2013, 09:32 
Заслуженный участник


12/09/10
1547
Руст в сообщении #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$

 Профиль  
                  
 
 Re: Целочисленные последовательности
Сообщение05.02.2013, 15:18 
Заслуженный участник


27/04/09
28128
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)$, дающие сюръективную последовательность?.. (Если их вдруг несчётное число, то я, конечно, не прошу. :lol:)

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

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

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

 Профиль  
                  
 
 Re: Целочисленные последовательности
Сообщение05.02.2013, 17:53 
Заслуженный участник


09/02/06
4397
Москва
arseniiv в сообщении #680261 писал(а):
(Если их вдруг несчётное число, то я, конечно, не прошу. :lol:)

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

 Профиль  
                  
 
 Re: Целочисленные последовательности
Сообщение05.02.2013, 20:32 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Целочисленные последовательности
Сообщение05.02.2013, 23:55 
Заслуженный участник


09/02/06
4397
Москва
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<...$ (все равно таких последовательностей континиум).

 Профиль  
                  
 
 Re: Целочисленные последовательности
Сообщение05.02.2013, 23:56 
Аватара пользователя


01/12/11

8634
arseniiv в сообщении #680015 писал(а):
(Здесь $\mathbb N$ имеется в виду с нулём.)

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

 Профиль  
                  
 
 Re: Целочисленные последовательности
Сообщение06.02.2013, 00:14 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Целочисленные последовательности
Сообщение06.02.2013, 13:40 
Заслуженный участник


27/04/09
28128
Не совсем, ноль используется ещё в значении $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)$, правда, была упущена.

 Профиль  
                  
 
 Re: Целочисленные последовательности
Сообщение06.02.2013, 14:26 
Заслуженный участник


09/02/06
4397
Москва
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$. Получаем с конечным или бесконечным уровнем фрактальное решение.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

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



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

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


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

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