ГЛАВНАЯ » РЕШЕБНИК

2019-05-06   
Доказать, что в равенстве

$N = \frac{N}{2} + \frac{N}{4} + \frac{N}{8} + \cdots + \frac{N}{2^n} + \cdots$

($N$ - произвольное целое положительное число) можно заменить все дроби ближайшими к ним целыми числами:

$N = \left ( \frac{N}{2} \right ) + \left ( \frac{N}{4} \right ) + \left ( \frac{N}{8} \right ) + \cdots + \left ( \frac{N}{2^n} \right ) + \cdots$.


Решение:


Первое решение. Очевидно, что $(a) = \left [a + \frac{1}{2} \right ]$ таким образом, равенство, которое нам требуется доказать, принимает вид

$N = \left [ \frac{N}{2} + \frac{1}{2} \right ] + \left [ \frac{N}{4} + \frac{1}{2} \right ] + \left [ \frac{N}{8} + \frac{1}{2} \right ] + \cdots$.

Пусть теперь

$N = a_n \cdot 2^n + a_{n-1} \cdot 2^{n-1} + \cdots + a_1 \cdot 2 + a_0$

($a_n, a_{n-1}, \cdots, a_1, a_0$ равны 0 или 1) - разложение числа $N$ по степеням двойки (запись $N$ в двоичной системе счисления). В таком случае, очевидно:

$\left [ \frac{N}{2} + \frac{1}{2} \right ] = \left [ a_n \cdot 2^{n-1} + a_{n-1} \cdot 2^{n-1} + \cdot + a_1 + \frac{a_0 + 1}{2} \right ] = a_n \cdot 2^{n-1} + a_{n-1} \cdot 2^{n-2} + \cdot + a_1 + a_0$,

$\left [ \frac{N}{4} + \frac{1}{2} \right ] = \left [ a_n \cdot 2^{n-2} + a_{n-1} \cdot 2^{n-3} + \cdot + a_1 + \frac{a_1 + 1}{2} + \frac{a_0}{4} \right ] = a_n \cdot 2^{n-2} + a_{n-1} \cdot 2^{n-3} + \cdot + a_1$,
$\cdots$
$\left [ \frac{N}{2^n} + \frac{1}{2} \right ] = \left [ a_n + \frac {a_{n-1} + 1}{2} + \frac{a_{n-2}}{4} + \cdots + \frac{a_0}{2^n} \right ] = a_n + a_{n-1}$,
$\left [ \frac{N}{2^{n+1}} + \frac{1}{2} \right ] = \left [ \frac{a_0+1}{2} + \frac{a_{n-1}}{4} + \cdots + \frac{a_0}{2^{n+1}} \right ] = a_n$

и

$\left [ \frac{N}{2^{n+2}} + \frac{1}{2} \right ] = \left [ \frac{N}{2^{n+3}} + \frac{1}{2} \right ] = \cdots = 0$

(напоминаем, что $a_n, \cdots, a_{0}$ равны 0 или 1). Таким образом, имеем:

$\left [ \frac{N}{2} + \frac{1}{2} \right ] + \left [ \frac{N}{4} + \frac{1}{2} \right ] + \cdots + \left [ \frac{N}{2^{n+1}} + \frac{1}{2} \right ] + \cdots = a_n(2^{n-1} + 2^{n-2} + \cdots + 1 + 1) + a_{n-1} (2^{n-2} + 2^{n-3} + \cdots + 1 + 1) + \cdots + a_1 (1+1) + a_0 = a_n2^n + a_{n-1} \cdot 2^{n-1} + \cdots + a_1 \cdot 2 + a_0 = N$,

что и требовалось доказать.

Второе решение. Очевидно, что число нечетных чисел не превосходящих $N$ равно $\frac{N}{2}$, если $N$ четно, и равно $\frac{N+1}{2} = \left [ \frac{N}{2} \right ] + 1$, если $N$ нечетно, т. е. равно $\left ( \frac{N}{2} \right )$. Точно так же число не превосходящих $N$ четных чисел, не делящихся на 4, равно $\left [ \frac{N}{4} \right ]$, если $N$ делится на 4 или дает при делении на 4 остаток 1, и равно $\left [ \frac{N}{4} \right ] + 1$, если $N$ дает при делении на 4 остаток 2 или 3; другими словами, это число всегда равно $\left ( \frac{N}{4} \right )$. Точно так же число не превосходящих $N$ чисел, делящихся на 4, но не делящихся на 8, равно $\left [ \frac{N}{4} \right ] $, если $N$ делится на 8 или дает при делании на 8 остатки 1, 2 или 3, и равно $\left [ \frac{N}{8} \right ]+1$ в противном случае, т. е. это число всегда равно $\left ( \frac{N}{8} \right )$. Аналогично доказывается, что $\left ( \frac{N}{16} \right )$ равно числу не превосходящих $N$ чисел, делящихся на 8 и не делящихся на 16; $\left ( \frac{N}{32} \right )$ равно числу не превосходящих $N$ чисел, делящихся на 16, но не делящихся на 32, и т. д. Таким образом мы переберем все целые числа от 1 до $N$; следовательно,

$\left ( \frac{N}{2} \right ) + \left ( \frac{N}{4} \right ) + \left ( \frac{N}{8} \right ) + \cdots = N$,

что и требовалось доказать.