Разделы 
Дополнительно
Задача по математике - 2896
2019-05-06 
Таблица из двух столбцов целых положительных чисел и какого-то числа строк выписывается по следующему правилу. В верхней строке мы пишем произвольные числа $a$ и $b$ далее под $a$ выписываем (целое положительное) число $a_1$, равное $\frac{a}{2}$ если $a$ четно, и равное $\frac{a-1}{2}$, если $a$ нечетно, а под $b$ выписываем число $b_1 = 2b$. Далее мы поступаем с числами $a_1$ и $b_1$ точно так же, как раньше поступили с числами $a$ и $b$: под $a_1$ мы пишем число $a_2$, равное $\frac{a_1}{2}$ если $a_1$ четно, и равное $\frac{a_1 -1}{2}$, если $a_1$ нечетно; под $b_1$ же мы пишем число $b_2 = 2b_1$. Под $a_2$ и $b_2$ мы располагаем числа $a_3$ и образованные из $a_2$ и $b_2$ точно так же, как числа $a_2$ и $b_2$ образуются из чисел $a_1$ и $b_1$, и т.д.; этот процесс мы кончаем в тот момент, когда доходим до некоторого числа $a_n = 1$ (которому отвечает число $b_n = 2b_{n-1}$). Доказать, что сумма всех стоящих в правом столбце чисел $b_i$, которым отвечают нечетные числа $a_i$ (здесь $i = 0, 1, \cdots, n$; под $a_0$ и $b_0$ мы понимаем числа $a$ и $b$), равна произведению $ab$.
Решение:
Запишем число $a$ в «двоичной системе счисления», т. е. в виде
$a = \alpha_n \cdot 2^n + \alpha_{n-1} \cdot 2^{n-1} + \alpha_{n-2} \cdot 2^{n-2} + \cdots + \alpha_1 \cdot 2 + \alpha_0 \cdot 1$,
где все «цифры» $\alpha_0, \alpha_1, \cdots, \alpha_{n-2}, \alpha_{n-1}, \alpha_n$ равны 0 или 1 (старшую «цифру» $\alpha_n$ числа $a$, разумеется, можно считать равной 1). Ясно, что если число $a$ четно, то $\alpha_0$ = 0 и $a_1 = \frac{a}{2} = \alpha_n \cdot 2^{n-1} + \alpha_{n-1} \cdot 2^{n-2} + \alpha_{n-2} \cdot 2^{n-3} + \cdots + \alpha_1 \cdot 1$; если же $a$ нечетно, то $\alpha_0 = 1$ - и число $a_1 = \frac{a-1}{2}$ имеет точно такое же строение. Таким образом, если $a$ записывается в двоичной системе счисления последовательностью «цифр» $a = \overline {\alpha_n \alpha_{n-1}\alpha_{n-2} \cdots \alpha_1\alpha_0}$, то $A_1$ записывается в той же системе счисления как $a_1 = \overline {\alpha_n \alpha_{n-1} \alpha_{n-2} \cdots \alpha_1}$, соответственно этому $a_2$ записывается как $a_2 = \overline {\alpha_n \alpha_{n-1} \cdots \alpha_2}$, $a_3$ - как $a_3 = \overline {\alpha_n \alpha_{n-1} \cdots \alpha_2}$, и т. д.- вплоть до числа $a_n = \alpha_n = 1$. С другой стороны, очевидно, $b_1 = 2b$, $b_2 = 2b_1 = 2^2b, b_3 = 2^3b$, и т. д. - вплоть до числа $b_n = 2^nb$.
Ясно, что $a_i = \overline {\alpha_n \alpha_{n-1} \cdots \alpha_1} = \alpha_n \cdot 2^{n-i} + \alpha_{n-1} \cdot 2^{n-i-1} + \cdots + \alpha_{i+1} \cdot 2 + \alpha_i \cdot 1$ (где $i = 0, 1, 2, \cdots , n$) будет нечетным, если «цифра» $\alpha_i$ равна 1 (напомним, что $\alpha_i$; может равняться лишь 0 или 1). Таким образом, в этом случае $b_i = 2^ib = (\alpha_i \cdot 2^i)b$. Поэтому интересующую нас сумму всех $b_i$ отвечающих нечетным $a_i$ можно записать так:
$[\alpha_n \cdot 2^n + \alpha_{n-1} \cdot 2^{n-1} + \cdots + \alpha_1 \cdot 2 + \alpha_0 \cdot 1] = \overline {\alpha_n \alpha_{n-1} \cdots \alpha_1 \alpha_0} \cdot b = ab$,
где в сумме $\alpha_n \cdot 2^n + \alpha_{n-1} \cdot 2^{n-1} + \cdots + \alpha_1 \cdot 2 + \alpha_0 \cdot 1 (= a)$ реально участвуют лишь слагаемые, отвечающие равным 1 значениям «цифр» $\alpha_n, \alpha_{n-1}, \cdots, \alpha_0$.
Таблица из двух столбцов целых положительных чисел и какого-то числа строк выписывается по следующему правилу. В верхней строке мы пишем произвольные числа $a$ и $b$ далее под $a$ выписываем (целое положительное) число $a_1$, равное $\frac{a}{2}$ если $a$ четно, и равное $\frac{a-1}{2}$, если $a$ нечетно, а под $b$ выписываем число $b_1 = 2b$. Далее мы поступаем с числами $a_1$ и $b_1$ точно так же, как раньше поступили с числами $a$ и $b$: под $a_1$ мы пишем число $a_2$, равное $\frac{a_1}{2}$ если $a_1$ четно, и равное $\frac{a_1 -1}{2}$, если $a_1$ нечетно; под $b_1$ же мы пишем число $b_2 = 2b_1$. Под $a_2$ и $b_2$ мы располагаем числа $a_3$ и образованные из $a_2$ и $b_2$ точно так же, как числа $a_2$ и $b_2$ образуются из чисел $a_1$ и $b_1$, и т.д.; этот процесс мы кончаем в тот момент, когда доходим до некоторого числа $a_n = 1$ (которому отвечает число $b_n = 2b_{n-1}$). Доказать, что сумма всех стоящих в правом столбце чисел $b_i$, которым отвечают нечетные числа $a_i$ (здесь $i = 0, 1, \cdots, n$; под $a_0$ и $b_0$ мы понимаем числа $a$ и $b$), равна произведению $ab$.
Решение:
Запишем число $a$ в «двоичной системе счисления», т. е. в виде
$a = \alpha_n \cdot 2^n + \alpha_{n-1} \cdot 2^{n-1} + \alpha_{n-2} \cdot 2^{n-2} + \cdots + \alpha_1 \cdot 2 + \alpha_0 \cdot 1$,
где все «цифры» $\alpha_0, \alpha_1, \cdots, \alpha_{n-2}, \alpha_{n-1}, \alpha_n$ равны 0 или 1 (старшую «цифру» $\alpha_n$ числа $a$, разумеется, можно считать равной 1). Ясно, что если число $a$ четно, то $\alpha_0$ = 0 и $a_1 = \frac{a}{2} = \alpha_n \cdot 2^{n-1} + \alpha_{n-1} \cdot 2^{n-2} + \alpha_{n-2} \cdot 2^{n-3} + \cdots + \alpha_1 \cdot 1$; если же $a$ нечетно, то $\alpha_0 = 1$ - и число $a_1 = \frac{a-1}{2}$ имеет точно такое же строение. Таким образом, если $a$ записывается в двоичной системе счисления последовательностью «цифр» $a = \overline {\alpha_n \alpha_{n-1}\alpha_{n-2} \cdots \alpha_1\alpha_0}$, то $A_1$ записывается в той же системе счисления как $a_1 = \overline {\alpha_n \alpha_{n-1} \alpha_{n-2} \cdots \alpha_1}$, соответственно этому $a_2$ записывается как $a_2 = \overline {\alpha_n \alpha_{n-1} \cdots \alpha_2}$, $a_3$ - как $a_3 = \overline {\alpha_n \alpha_{n-1} \cdots \alpha_2}$, и т. д.- вплоть до числа $a_n = \alpha_n = 1$. С другой стороны, очевидно, $b_1 = 2b$, $b_2 = 2b_1 = 2^2b, b_3 = 2^3b$, и т. д. - вплоть до числа $b_n = 2^nb$.
Ясно, что $a_i = \overline {\alpha_n \alpha_{n-1} \cdots \alpha_1} = \alpha_n \cdot 2^{n-i} + \alpha_{n-1} \cdot 2^{n-i-1} + \cdots + \alpha_{i+1} \cdot 2 + \alpha_i \cdot 1$ (где $i = 0, 1, 2, \cdots , n$) будет нечетным, если «цифра» $\alpha_i$ равна 1 (напомним, что $\alpha_i$; может равняться лишь 0 или 1). Таким образом, в этом случае $b_i = 2^ib = (\alpha_i \cdot 2^i)b$. Поэтому интересующую нас сумму всех $b_i$ отвечающих нечетным $a_i$ можно записать так:
$[\alpha_n \cdot 2^n + \alpha_{n-1} \cdot 2^{n-1} + \cdots + \alpha_1 \cdot 2 + \alpha_0 \cdot 1] = \overline {\alpha_n \alpha_{n-1} \cdots \alpha_1 \alpha_0} \cdot b = ab$,
где в сумме $\alpha_n \cdot 2^n + \alpha_{n-1} \cdot 2^{n-1} + \cdots + \alpha_1 \cdot 2 + \alpha_0 \cdot 1 (= a)$ реально участвуют лишь слагаемые, отвечающие равным 1 значениям «цифр» $\alpha_n, \alpha_{n-1}, \cdots, \alpha_0$.
