Тождество с целой частью [Теория чисел]

[Whitaker]

Здравствуйте, уважаемые друзья!

Мне нужно доказать, что верно следующее тождество для $p\in \mathbb{Z}:$ $0\leqslant p \leqslant {2^k-1}$ и $r\in \mathbb{N}$

$$\left[\dfrac{2^k-1}{2^r}\right]=\left[\dfrac{p}{2^r}\right]+\left[\dfrac{2^k-p-1}{2^r}\right]$$

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

С уважением, Whitaker.

[ИСН]

Тут следует задаться более общим вопросом: когда $\lfloor{a+b\over c}\rfloor = \lfloor{a\over c}\rfloor + \lfloor{b\over c}\rfloor$?

[Sonic86]

ИСН в сообщении #630572 писал(а):

Тут следует задаться более общим вопросом: когда $\lfloor{a+b\over c}\rfloor = \lfloor{a\over c}\rfloor + \lfloor{b\over c}\rfloor$?

В частности, оно не всегда верно даже при $a=b$.

[Руст]

ИСН в сообщении #630572 писал(а):

Тут следует задаться более общим вопросом: когда $\lfloor{a+b\over c}\rfloor = \lfloor{a\over c}\rfloor + \lfloor{b\over c}\rfloor$?

Оно всегда верно, в рассматриваемом случае, когда $c|a+b+1$.

[ИСН]

Вот то-то и оно.

[Whitaker]

Получается, что данное тождество верно?
Ведь $a+b+1=p+(2^k-p-1)+1=2^k$ и $c=2^r$
$c\mid a+b+1$, т.е. $2^r\mid 2^k$ при $r\leqslant k$
P.S. При $r>k$ получается, что: $\left[\dfrac{2^k-1}{2^r}\right]=\left[\dfrac{2^k-p-1}{2^r}\right]=\left[\dfrac{p}{2^r}\right]=0$

-- Вс окт 14, 2012 10:20:34 --

Руст
А как вообще доказать, что если $c\mid a+b+1$, то $\left[\dfrac{a+b}{c}\right]=\left[\dfrac{a}{c}\right]+\left[\dfrac{b}{c}\right]$?
P.S. В данном случае $a,b,c \in \mathbb{Z}$?

[Whitaker]

Пытаюсь вывести разными способами из $c\mid a+b+1$ то, что $\left[\frac{a+b}{c}\right]=\left[\frac{a}{c}\right]+\left[\frac{b}{c}\right]$, но ничего не выходит
Было бы интересно прочитать ваши идеи по этому поводу

[Руст]

Whitaker в сообщении #630683 писал(а):

Пытаюсь вывести разными способами из $c\mid a+b+1$ то, что $\left[\frac{a+b}{c}\right]=\left[\frac{a}{c}\right]+\left[\frac{b}{c}\right]$, но ничего не выходит
Было бы интересно прочитать ваши идеи по этому поводу

Очень просто. Привыполнении $c|a+b+1$ число $a+b=kc+(c-1)$. Если $a=k_1c+r_1,b=k_c+r_2$, то $a+b=(k_1+k_2)c+r_1+r_2$. Так как $r_i\le c-1$, то $r_1+r_2<c+c-1$ (случай $r_1+r_2=c+(c-1)$ невозможен), следовательно $r_1+r_2=c-1,k_1+k_2=k$, что и доказывает соотношение.

[Whitaker]

Руст
Если я Вас правильно понял, то $k=k_1+k_2$ и $r_1+r_2=c-1$ вытекает из сравнения коээфициентов в $a+b=c(k_1+k_2)+(r_1+r_2)$ и $a+b=ck+(c-1)$?

Руст в сообщении #630691 писал(а):

$b=k_c+r_2$

Здесь Вы наверное хотели написать $b=k_2c+r_2$

[Руст]

все верно.

[Whitaker]

Руст
Большое Вам СПАСИБО за помощь!
Впервые узнал что такое тождество выполняется при таком условии