Утверждение с неравенствами и целочисленными функциями

[kisupov]

Добрый день. Возникла следующая задачка.
Имеется возрастающая последовательность натуральных чисел

$$ \{v_1,v_2,\ldots,v_g\}, $$

причем

$$ v_i=\left\lfloor \log_2 \frac{P-1}{\psi P-1}\right\rfloor, \quad i = 1,\ldots,g-1, $$

$$ v_g=\left\lceil \log_2\psi P\right\rceil, $$

где $P$ - натуральное число, $0< \psi < 1$ - вещественное.

Необходимо доказать утверждение:

$$ \forall x \in\{1,2,\ldots,\psi P - 1\} \exists j \in \{1,2,\ldots,g\} : \psi P \le x \cdot 2^{v_j} \le P - 1. $$

При необходимости, сузить интервал изменения $\psi$.


Что здесь смущает - так это целочисленные функции $\lceil\cdot\rceil$ и $\lfloor \cdot \rfloor$. Пробовал доказывать вначале для граничных значений $x$: в одном случае не возникает проблем с первым неравенством, а в другом - со вторым. К примеру, если $x = 1$, то, выбирая $j = g$ и логарифмируя, имеем:

$$ \log_2 \psi P \le \left\lceil \log_2\psi P\right\rceil, $$

Напротив, при $x = \psi P - 1$ достаточно взять $j = 1$. Так как

$$ 2^{\left\lfloor \log_2 \frac{P-1}{\psi P-1}\right\rfloor} \le \frac{P-1}{\psi P-1}, $$

то

$$ (\psi P - 1)\cdot\left\lfloor \log_2 \frac{P-1}{\psi P-1}\right\rfloor \le (\psi P - 1)\cdot\frac{P-1}{\psi P-1} \le P-1 $$

В обоих этих случаях достаточно, чтобы $\psi \le 1$. Как действовать дальше - я не знаю, может быть у вас будут идеи?

[mihiv]

kisupov в сообщении #816650 писал(а):

$$ v_i=\left\lfloor \log_2 \frac{P-1}{\psi P-1}\right\rfloor, \quad i = 1,\ldots,g-1, $$

В правой части равенства нет индекса $i$ ?

[kisupov]

mihiv в сообщении #816695 писал(а):

kisupov в сообщении #816650 писал(а):

$$ v_i=\left\lfloor \log_2 \frac{P-1}{\psi P-1}\right\rfloor, \quad i = 1,\ldots,g-1, $$

В правой части равенства нет индекса $i$ ?

прошу прощения, опечатался:

$$ v_i=i\cdot\left\lfloor \log_2 \frac{P-1}{\psi P-1}\right\rfloor, \quad i = 1,\ldots,g-1, $$

Для примера, если $P=2^{128}, \psi = 2^{-42}$, то указанному утверждению удовлетворяет последовательность

$$ \{42, 84, 86\}, $$

причем для $x\in[1, 2^2-1]$ следует выбрать $v_3 = 86$, для чисел $x\in[2^2, 2^{44}-1]$ - $v_2 = 84$, а для чисел $x\in[2^{44}, 2^{86}-1]$ - $v_1 = 42$.