функции "пол" и "потолок"

[kisupov]

Здравствуйте. Имеется пара задачек на функции $\lfloor\cdot\rfloor$ и $\lceil\cdot\rceil$, а именно:

1. в равенстве $x = \lceil y \cdot z \rceil$, где $y $ - целое неотрицательное число, а $z$ - рациональная константа, вынести $y$ за знак потолка.

2. даны $x$ и $x'$ - дробные числа из открытого интервала $(0, 1)$, причем $x' = x + \Delta x$, а также натуральное число $v$. Необходимо определить максимально допустимое значение $\Delta x$, при котором выполняется равенство: $\lfloor x\cdot 2^v \rfloor = \lfloor x'\cdot 2^v \rfloor$.

Подскажите пожалуйста, разрешимы ли эти задачки в такой постановке (в особенности интересует первая задача) и если разрешимы, то как их решить или хотя бы с чего начать решение...

[arseniiv]

А вы сделайте небольшую таблицу значений $\lceil yz \rceil$ в зависимости от $y$, взяв числитель и знаменатель $z$ небольшими — например, $z = \frac25$, а потом $z = \frac43$. Может, какую-то закономерность подметите.

[kisupov]

Спасибо за совет. Попробую. Но все же хотелось бы узнать, может быть есть по этому поводу какие-то результаты в теории чисел? Чтобы и обоснование было, и велосипед не сочинять.

[arseniiv]

Сначала лучше увидеть, тогда будет понятно, как это выражается и почему.

[kisupov]

построил таблички, при первом взгляде закономерность какую-либо определить не удалось. как можно вынести целочисленный множитель за знак пола?

[arseniiv]

Хм. Похоже, $y$ и нельзя вынести. Для пола получается ($\mathrm{\text{НОД}}(p,q)=1$)

$$\left\lfloor\frac{pn}q\right\rfloor = p\left\lfloor\frac nq\right\rfloor + \left\lfloor(n\bmod q)\frac pq\right\rfloor.$$

Посмотрите Кнута, Грэхема, Паташника «Конкретная математика». Там на тему полов и потолков целая глава.

[kisupov]

книжку эту я смотрел, но подходящего не нашел. а по второй задачке может быть что-то подскажите?

[provincialka]

Вторая задача. Если $x, v$ -постоянны, то левая часть равенства также постоянна. Тогда для $x'y$ можно записать неравенства.

[kisupov]

Представим числа $x$ и $x'$ в виде взвешенных сумм разрядов:

$$ (1) \qquad x=\sum\limits_{i=0}^{\infty}{{{b}_{i}}\cdot {{2}^{-i}}}, \quad {x}'=\sum\limits_{i=0}^{\infty }{{{d}_{i}}\cdot {{2}^{-i}}}, $$

Пусть ${d}_{\rho }$ – первый ошибочный разряд в двоичном представлении ${x}'$. Тогда если $\Delta x<{{2}^{-v}}$, то ${{b}_{i}}={{d}_{i}},i=0,1,...,v$, а $\rho \ge v+1$. Умножение чисел (1) на степень двойки ${{2}^{v}}$ не приводит к изменению значений разрядов ${{b}_{i}}$ и ${{d}_{i}}$, а меняет лишь значения их весов. При этом

$$(2) \qquad x\cdot {{2}^{v}}=\sum\limits_{i=1}^{\infty }{{{d}_{i}}\cdot {{2}^{-i+v}}}, \quad{x}'\cdot {{2}^{v}}=\sum\limits_{i=1}^{\infty }{{{d}_{i}}\cdot {{2}^{-i+v}}}.$$

Таким образом, индекс ошибочного разряда остается неизменным. При округлении в соответствии с функцией $\left\lfloor \cdot \right\rfloor $ все слагаемые сумм (2), начиная с $i=j=v+1$ отбрасываются (заменяются нулями), при этом отбрасывается также и ошибочное слагаемое, если оно имеет вес $\rho \ge v+1$. И напротив, если $\rho \le v$, то его значение попадет в результатную целую часть $\left\lfloor {{x}'} \right\rfloor $. Таким образом, искомое неравенство:

$$\Delta x<{{2}^{-v}}.$$

Подскажите пожалуйста, верны ли эти рассуждения?

[provincialka]

Все еще непонятно. Вы $\Delta x$ подбираете сразу для всех $x$, или для каждого? А то у вас в условии все названо "заданным": и $x$, и $v$, и даже $x'$.
Если $x,x'$ даны, то $\Delta x$ - это их разность, что тут максимизировать?

[kisupov]

приношу извинения за некорректную формулировку. В оригинале задача звучит так:

определить максимальное отклонение $\Delta x$, при котором $\lfloor x\cdot 2^v \rfloor = \lfloor x'\cdot 2^v \rfloor$, где $x' = x + \Delta x$ для всех $x \in (0, 1)$. Показатель $v$ --- целое неотрицательное число.

[provincialka]

Ваше условие можно переписать в виде $k\le x\cdot2^v <x'\cdot 2^v<k+1$, где $k$ - общее значение целых частей. Отсюда следует ограничение на $\Delta x$. Но для доказательства обратного соотношения нужно потребовать еще, что $x'<1$, без этого ограничения $\Delta x=0$.

-- 11.10.2013, 21:47 --

Кстати, среди значений $\Delta x$ нет максимального, есть только супремум.

[kisupov]

извините, что-то не соображу, какое следует ограничение на $\Delta x$ из написанного вами условия? Можно его как-то выразить через $v$? Для определенности будем полагать, что $x' < 1$. И еще хотелось бы узнать, в приведенных мною выше рассуждениях есть какой-то смысл?:)

[provincialka]

Ну, не хотелось бы давать полного решения... Два числа $x\cdot2^v,x'\cdot2^v$ лежат в одном промежутке длиной 1. Какой может быть разность между ними?

-- 11.10.2013, 22:00 --

Ваше рассуждение в общем верно, только трудно читать. И оно какое-то нестрогое. Какие-то взвешенные суммы, когда это просто двоичное разложение. Мне кажется, все можно сделать короче и яснее, без рядов.
а уж если пользуетесь рядами, упомяните, что коэффициенты не могут быть все равны 1, начиная с некоторого.

[kisupov]

Полагаю $\sup \Delta x = 2^{-v}$. Про какое обратное соотношение вы говорили? Имеется ввиду необходимое условие? Да, здесь ясно, что если $x' > 1$, то исходное условие изначально нарушится.