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

[maxal]

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

Докажите (или опровергните ), что для $p\geq 1$:

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

[mihaild]

Я, видимо, опять не могу прочитать условия. Последовательность $1, p$ разве не является опосредованной при $p > 1$?

[maxal]

mihaild, ноль там обязан присутствовать.

[Null]

Для 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$

[maxal]

Null, почему нельзя короче?

[mihaild]

Потому что $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}$.

[Null]

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