2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 опосредованные последовательности
Сообщение18.12.2019, 01:02 
Модератор
Аватара пользователя


11/01/06
5660
Возрастающую последовательность целых чисел $s_0=0 < s_1 < \dots < s_n = p$ назовем опосредованной, если каждый член $s_i$ для $0<i<n$ равен среднему арифметическому каких-то двух других членов последовательности.
Пусть $L(p,q)$ обозначает минимальную длину опосредованной последовательности, заканчивающейся на $p$ и содержащей $q$.

Докажите (или опровергните :wink:), что для $p\geq 1$:
  • $L(p,1) = \lceil \log_2 p\rceil + 2$
  • Для всякого целого $q<p$ взаимно простого с $p$, имеем $L(p,q) = L(p,1)$

 Профиль  
                  
 
 Re: опосредованные последовательности
Сообщение18.12.2019, 01:10 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
Я, видимо, опять не могу прочитать условия. Последовательность $1, p$ разве не является опосредованной при $p > 1$?

 Профиль  
                  
 
 Re: опосредованные последовательности
Сообщение18.12.2019, 01:14 
Модератор
Аватара пользователя


11/01/06
5660
mihaild, ноль там обязан присутствовать.

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


12/08/10
1608
Для 1ого пункта пример можно получить операциями $S_{2p-1}=S_p\cup\{2p-1\}$ и $S_{2p}=\{2i|i \in S_p\}\cup\{1\}$ из множества $S_2=\{0,1,2\}$. Все получившиеся множества включают $0, 1, 2$

 Профиль  
                  
 
 Re: опосредованные последовательности
Сообщение19.12.2019, 13:28 
Модератор
Аватара пользователя


11/01/06
5660
Null, почему нельзя короче?

 Профиль  
                  
 
 Re: опосредованные последовательности
Сообщение19.12.2019, 13:48 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
Потому что $s_n \leqslant 2^{n - 1}$. По индукции: если $s_{n - 1} \leqslant 2^{n - 2}$ - не последний член, то он среднее каких-то $s_i = s_{n - 1} - k$ и $s_j = s_{n - 1} + k$. Т.к. $k \leqslant 2^{n - 2}$, то $s_j \leqslant 2^{n - 1}$.

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


12/08/10
1608
Для $p=2^k$ и нечетного $q$ $L(p,q) = k+2$.

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

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



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

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


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

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