«Квант» — научно-популярный физико-математический журнал (издаётся с 1970 года)
Старый сайт журнала: kvant.ras.ru

Задача М844

Условие задачи (1984, № 1) Задача М844 // Квант. — 1984. — № 1. — Стр. 42—43; 1984. — № 4. — Стр. 36—37.

  1. Докажите, что любое натуральное число $a$‍‍ можно единственным образом представить в виде $$ a=a_1\cdot1!+a_2\cdot2!+\ldots+a_n\cdot n!, \tag{1} $$ где $a_k$‍‍ — целые числа, $0\le a_k \le k$‍,$a_n\neq0$‍.‍ (По определению, $k!=1 \cdot 2 \cdot \ldots \cdot k$‍,$1!=1.$‍)
  2. Докажите, что любое рациональное число $r$‍,$0 \le r<1$‍,‍ можно единственным образом представить в виде $$ r=\dfrac{b_1}{2!}+\dfrac{b_2}{3!}+\ldots+\dfrac{b_n}{(n+1)!}, \tag{2} $$ где $b_k$‍‍ — целые числа, $0\le b_k\le k$‍,$b_n\neq 0$‍.
  3. Представьте в виде $(1)$‍‍ число $a=1984$‍‍ и в виде $(2)$‍‍ число $r=\dfrac{19}{84}$‍.

В. Е. Колосов


Решение задачи (1984, № 4) Задача М844 // Квант. — 1984. — № 1. — Стр. 42—43; 1984. — № 4. — Стр. 36—37.

а) Покажем, как по данному числу $a$‍‍ найти старший коэффициент $a_n$‍‍ в представлении $$ a=a_1\cdot1!+a_2\cdot2!+\ldots+a_{n-1}\cdot(n-1)!+a_n\cdot n!\tag{*} $$ где $0\le a_k\le k$‍,$a_n\ne0$‍,‍ и его номер $n$‍.

$$ \begin{gather*} 1\cdot1!+2\cdot2!+\ldots+n\cdot n!=(2!-1!)+(3!-2!)+\ldots+((n+1)!-n!)=(n+1)!-1\tag{А}\\\\ \dfrac n{(n+1)!}+\dfrac{n-1}{k!}+\ldots+\dfrac k{(k+1)!}=\dfrac1{k!}-\dfrac1{(n+1)!}\tag{Б} \end{gather*} $$

Из тождества (А) следует, что при указанных значениях коэффициентов $a_k$‍‍ $$ \begin{gather*} a'=a_1\cdot1!+a_2\cdot2!+\ldots+a_{n-1}\cdot(n-1)!\le\\ \le1\cdot1!+2\cdot2!+\ldots+(n-1)\cdot(n-1)!\lt n!, \end{gather*} $$ кроме того, $n!\le a_n\cdot n!\le n\cdot n!$‍.‍ Для каждого натурального $a$‍‍ можно найти единственное $n$‍‍ такое, что $a$‍‍ лежит в промежутке $n!\le a\lt(n+1)!$‍;‍ этим однозначно определяется $n$‍‍ в представлении (*). Разбив этот промежуток на $n$‍‍ промежутков (длиной $n!$‍‍ каждый), мы найдём единственное возможное значение $a_n$‍‍ как номер того промежутка, куда попадает $a$‍:$a_n\cdot n!\le a\lt(a_n+1)n!$‍;‍ другими словами, $a_n$‍‍ — неполное частное от деления $a$‍‍ на $n!$‍:$a=a_n\cdot n!+a'$‍,‍ где $0\le a'\lt n!$‍$\Big(a_n=\left[\dfrac{a}{n!}\right]$‍,‍ где $[x]$‍‍ — целая часть $x$‍).

Точно так же мы можем найти для $a'$‍‍ старший коэффициент в представлении $$ a'=a_1\cdot1!+a_2\cdot2!+\ldots+a_{n-1}\cdot(n-1)! $$ и т. д. Формальное доказательство существования и единственности требуемого представления (*) можно провести методом математической индукции: для $a=1$‍‍ утверждение очевидно, а наше рассуждение показывает, как из предположения, что оно верно для чисел, меньших $a$‍,‍ следует его справедливость для данного $a$‍.

Можно двигаться и в обратном направлении: сначала найти $a_1$‍,‍ потом $a_2$‍‍ и т. д. При этом $a_1$‍‍ есть остаток от деления $a$‍‍ на 2, $a_2$‍‍ — остаток от деления $\dfrac{a-a_1\cdot 1!}2$‍‍ на 3 и, вообще, $a_k$‍‍ — остаток от деления $\dfrac{a-a_1\cdot 1!-\ldots-a_{k-1}\cdot(k-1)!}{k!}$‍‍ на $k+1$‍.

Оба эти способа позволяют вывести такую общую формулу для $a_k$‍:‍ $$ a_k=\left[\dfrac a{k!}\right]-\left[\dfrac a{(k+1)!}\right](k+1). $$

б) Будем последовательно разбивать отрезок $[0;1]$‍:‍ на 1-м шагу — на 2 равные части, на 2-м шагу каждый из двух образовавшихся отрезков — на 3 равные части и т. д. Вообще, на $k$‍‍-м шагу каждый из отрезков, полученных на $(k-1)$‍‍-м шагу, разбивается на $k+1$‍‍ равных частей. Ясно, что после $k$‍‍-го шага отрезок $[0;1]$‍‍ будет разбит на $(k+1)!$‍‍ равных частей.

Рассмотрим точку разбиения $r$‍,‍ появившуюся впервые на $n$‍‍-м шагу (очевидно, $r=\dfrac m{(n+1)!}$‍,‍ где $m$‍‍ не делится на $n+1$‍).‍ Эта точка отстоит от ближайшей к ней слева точки $(n-1)$‍‍-го шага на величину $\dfrac{b_n}{(n+1)!}$‍,‍ где $b_n$‍‍ — целое число, $0\lt b_n\le n$‍.‍ В свою очередь, эта точка $(n-1)$‍‍-го шага отстоит от ближайшей слева точки $(n-2)$‍‍-го шага на $\dfrac{b_{n-1}}{n!}$‍,‍ где $0\le b_{n-1}\le n-1$‍,‍ и т. д. В итоге получим представление $$ r=\dfrac{b_1}{2!}+\dfrac{b_2}{3!}+\ldots+\dfrac{b_n}{(n+1)!},\quad0\le b_k\le k,\quad b_n\ne0.\tag{**} $$ Его единственность следует из того, что при любом наборе $b_1$‍,$\ldots$‍,$b_n$‍‍ в (**) числа $$ \dfrac{b_1}{2!},\quad\dfrac{b_1}{2!}+\dfrac{b_2}{3!},\quad\ldots,\quad \dfrac{b_1}{2!}+\dfrac{b_2}{3!}+\ldots+\dfrac{b_n}{(n+1)!} $$ получаются, соответственно, не позже чем на 1-м, 2-м, $\ldots$‍,$n$‍‍-м шагах разбиения, причём (в силу неравенств $0 \le b_k\le k$‍‍ каждое из них является ближайшим слева к следующему среди всех чисел того же шага.

Остаётся заметить, что любое рациональное число $r=\dfrac pq$‍‍ из промежутка $[0;1]$‍‍ появится среди точек разбиения не позже чем на $(q-1)$‍‍-м шагу, так как $r=\dfrac{p(q-1)!}{q!}$‍.

Фактически в этом решении коэффициенты $b_1$‍,$\ldots$‍,$b_n$‍‍ определяются последовательно начиная с $b_n$‍:‍ если уже найдены $b_n$‍,$\ldots$‍,$b_k$‍,‍ то $b_{k-1}$‍‍ — это остаток от деления (целого!) числа $\left(r-\dfrac{b_n}{(n+1)!}-\ldots-\dfrac{b_k}{(k+1)!}\right)\cdot k!$‍‍ на $k$‍.‍ Подумайте, как можно находить эти коэффициенты начиная с $b_1$‍.‍ Проверьте справедливость следующей формулы: $$ b_k=[r\cdot(k+1)!]-[r\cdot k!](k+1) $$ (можно использовать тождество (Б)).

в) Ответ: $1984=2\cdot2!+3\cdot3!+2\cdot4!+4\cdot5!+2\cdot6!$‍,$\dfrac{19}{84}=\dfrac1{3!}+\dfrac1{4!}+\dfrac2{5!}+\dfrac6{7!}$‍.‍ Эти представления легко найти, опираясь на решения пунктов а) и б).

В. Е. Колосов


Метаданные Задача М844 // Квант. — 1984. — № 1. — Стр. 42—43; 1984. — № 4. — Стр. 36—37.

Предмет
Математика
Условие
Решение
Номера

1984. — № 1. — Стр.  [условие]

1984. — № 4. — Стр.  [решение]

Описание
Задача М844 // Квант. — 1984. — № 1. — Стр. 42‍—‍43; 1984. — № 4. — Стр. 36‍—‍37.
Ссылка
https://www.kvant.digital/problems/m844/