Описание Часть 1

Описание Часть 2

Условия задач

Решения задач

 

Часть 1

1.1 Может период десятичной дроби оканчиваться нулем?

Может! Не следует путать цифры периода с остатками при делении «уголком». Как было замечено, наличие нулевого остатка указывает на конечность десятичной дроби. Однако среди цифр периода 0 может присутствовать, в том числе в конце. Пример: $0,(90) = \frac{10}{11}$.

1.2а) Приведите пример числа меньшего 0,000001, представимого бесконечной периодической десятичной дробью с предпериодом. б) Может «чисто-периодическая» десятичная дробь быть меньше 0,000001?

а) Следует взять предпериод из 6 нулей или начинающийся 6 нулями, например: 0,000000(8) или 0,0000009(8).

б) Может. Для этого период должен начинаться 6 нулями, например: 0,(0000009).

1.3 Какая из нижеперечисленных десятичных дробей представляется правильной обыкновенной дробью со знаменателем, не кратным 2 и 5:
 а) $0,(99)$;   б) $0,54(5)$;   в) $0,32(5432)$;   г) $0,32(9)$?

а) $0,(99)\;=\;0,9999\dots\;=\;0.(9)\;=\;1$  не является правильной дробью. Не подходит.
б) $0,54(5)\;=\;0,545555\dots...$  содержит предпериод, поэтому знаменатель кратен 2 или 5. Не подходит.
в) $0,32(5432)\;=\;0,3254325432\dots \;=\;0,(3254)$  можно записать в виде «чисто-периодической» десятичной дроби, поэтому знаменатель соответствующей несократимой дроби не делится на 2 и на 5. Подходит.
г) $0.32(9)\;=\;0.33$  конечная дробь. Знаменатель соответствующей несократимой дроби не содержит простых делителей, кроме 2 и 5. Не подходит.

Ответ: в)

1.4В периодической десятичной дроби 0,242424… первую цифру после запятой заменили на 4. Во сколько раз полученное число больше исходного?

До изменения цифры: $$ a = 0,242424\ldots = 0,(24) = \frac{24}{99} = \frac{8}{33} $$

После изменения цифры: $$ b = 0,442424\ldots = 0,4(42) = \frac{442-4}{990} = \frac{73 \cdot 6}{33 \cdot 30} = \frac{73}{33 \cdot 5} $$

Таким образом $$ \frac{b}{a} = \frac{73}{33 \cdot 5}\;:\;\frac{8}{33} = \frac{73}{40} = 1,825 $$

1.5а) Всегда ли произведение бесконечных «чисто-периодических» дробей представляется бесконечной «чисто-периодической» дробью? b) Может произведение дробей с предпериодом представляться «чисто-периодической» дробью?

а) Так как, например $\frac{3}{7} \cdot \frac{7}{3} = 1$, следует «слегка уточнить формулировку»:

Произведение бесконечных «чисто-периодических» дробей является целым числом или представляется бесконечной «чисто-периодической» дробью.

Пусть $b_1, b_2, \dots b_n$ — знаменатели соответствующих обыкновенных дробей. Каждое из $b_i$ не содержит простых множителей 2 и 5. Перемножив дроби и произведя при необходимости сокращение, получим дробь, знаменатель $b$ которой является делителем $b_1b_2 \dots b_n$. Заметим, что $b$ также не делится на 2 и 5. Если $b=1$, произведение дробей — целое число, в противном случае оно представляется бесконечной число-периодической дробью.

В частности, произведение правильных бесконечных «чисто-периодических» дробей представляется бесконечной «чисто-периодической» дробью, поскольку оно заведомо не является целым числом.

б) Может. Знаменатели сомножителей выбираем так, что одни делятся на 2 но не на 5, другие делятся на 5 но не на 2, причем оба вида присутствуют. Подбираем числители так, чтобы дроби были несократимы, но в произведении все множители знаменателя, кратные 2 и 5 сокращались. Вот простой пример: $\frac{2}{15} \cdot \frac{5}{6} = \frac{1}{9}$. [В десятичной записи: $0,1(3) \times 0,8(3) = 0,(1)$.] Очевидно, это возможно только в системе счисления, основание которой составное число.

1.6Числа $A$ и $B$ задается правильными «чисто-периодическими» дробями, период которых начинается соответственно $p$ и $q$ нулями. Сколькими нулями может начинаться период десятичного представления произведения $AB$?

Пусть период числа $S$ длиной $m+n$ начинается $m$ нулями. Таким образом $$ S = \overline{0,\underbrace{00 \dots 0}_{m\;\text{нулей}}\,s_1s_2 \dots s_n \, \underbrace{00 \dots 0}_{m\;\text{нулей}}\,s_1s_2 \dots s_n \;\; \dots }, $$ где $s_1 \gt 0$.

Умножив на $10^m$, получаем: $$ 10^{\,m}S = \overline{0,\,s_1s_2 \dots s_n \, \underbrace{00 \dots 0}_{m\;\text{нулей}} \;\; \dots} $$

Ввиду $s_1 \gt 0$, получаем $0,1 \leqslant 10^{\,m}S \lt 1$,  откуда: или $$ 10^{-(m+1)} \leqslant S \lt 10^{-m} \label{eq:1.6.1}\tag{1.6.1} $$

Проводя рассуждения в обратную сторону, устанавливаем, что $\eqref{eq:1.6.1}$ является также достаточным условием для того, чтобы период бесконечной «чисто-периодической» дроби начинался $m$ нулями.

Обратимся теперь непосредственно к решению задачи. В предыдущей задаче выло установлено, что произведение правильных «чисто-периодических» дробей представляется «чисто-периодической» дробью. Для определения длины периода десятичного представления произведения, запишем: $$ \begin{array}{l} 10^{-(p+1)} \leqslant A \lt 10^{-p} \\ 10^{-(q+1)} \leqslant B \lt 10^{-q} \end{array} $$

Перемножив неравенства, получим: $$ \begin{array}{l} 10^{-(p+q+2)} \leqslant AB \lt 10^{-(p+q)} \\ \end{array} $$

Таким образом, произведение может оказаться в промежутке $\left[10^{-(p+q+2)}, 10^{-(p+q+1)}\right)$, при этом период начинается $(p+q+1)$ нулями, или в промежутке $\left[10^{-(p+q+1)}, 10^{-(p+q)}\right)$, с периодом, начинающимся $(p+q)$ нулями.

В качестве примера положим $p=0$, $q=1$. Произведение $0,(1) \times 0,(01) = \frac{1}{9} \times \frac{1}{99} = \frac{1}{891} = 0,(001122334455667789)$  содержит 2 нуля в начале периода, тогда как в произведении $0,(8) \times 0,(09) = \frac{8}{9} \times \frac{1}{11} = \frac{8}{99} = 0,(08)$  период начинается с одного нуля.

1.7Найти все пары натуральных чисел, удовлетворяющих равенству $\sqrt{xx,xxx\dots} = y,yyy\dots$. (B обеих частях равенства стоят бесконечные десятичные дроби, записанные с помощью цифр $x$  и  $y$)

Олимпиада «Покори Воробьевы горы!» 2013. Приводится собственное решение.

Переводя десятичные дроби в обыкновенные, получаем: $$ \begin{array}{l} \overline{xx,xxx\dots} = \overline{xx,(x)} = 11x + \dfrac{x}{9} = \dfrac{100}{9}x \\ \overline{y,yyy\dots} = \overline{y,(y)} = y + \dfrac{y}{9} = \dfrac{10}{9}y \end{array} $$ что позволяет переписать заданное уравнение в виде: $$ \dfrac{10}{3} \sqrt{x} = \frac{10}{9}y $$ откуда $$ x = \left(\frac{y}{3}\right)^2 \label{eq:1.7.1}\tag{1.7.1} $$

Таким образом $y$ — цифра, кратная 3. Поскольку 0 мы не считаем натуральным числом, а также договорились не рассматривать период $(9)$,   возможные значения $y$:  3 или 6. Из $\eqref{eq:1.7.1}$ получаем значения $x$: 1 и 4 соответственно.

При этом равенства принимают вид: $$ \begin{array}{l} \sqrt{11,(1)} = 3,(3), \quad \text{то есть} \quad \sqrt{11\frac{1}{9}} = 3\frac{1}{3} \quad \text{или} \quad \sqrt{\frac{100}{9}} = \frac{10}{3} \\ \sqrt{44,(4)} = 6,(6), \quad \text{то есть} \quad \sqrt{44\frac{4}{9}} = 6\frac{2}{3} \quad \text{или} \quad \sqrt{\frac{400}{9}} = \frac{20}{3} \end{array} $$

Ответ: $(x, y)$ равно (1,3) или (4,6).

1.8Какие из утверждений верны:
 а) Число представимое в виде конечной десятичной дроби представимо в виде конечной дроби в системе счисления с любым основанием;
 б) Число представимое в виде периодической десятичной дроби представимо в виде периодической дроби в системе счисления с любым основанием;
 в) Если десятичное представление дроби содержит предпериод, то $n$-ичное представление этой дроби содержит предпериод для любого целого $n \gt 1$?

а) Неверно. Как было замечено в разделе 3, для конечности $n$-ичного разложения дроби необходимо и достаточно, чтобы все простые множители знаменателя были делителями основания системы счисления $n$. Так как различные основания имеют различные простые множители, то конечная дробь в одной системе счисления может оказаться бесконечной в другой. Например, $\frac{1}{5}=0,2$ в восьмиричной системе счисления выражается бесконечной периодической дробью: $\frac{1}{5} = 0,(1463)_8$.

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

в) Неверно. Например, $\frac{1}{6}=0,1(6)$ имеет предпериод в десятичной системе, так как знаменатель 6 имеет общий делитель 2 с основанием системы счисления 10. Однако числа 6 и 5 взаимно простые, поэтому в пятиричной системе дробь не обладает предпериодом: $\frac{1}{6} = 0,(04)_5$.

1.9Число $\dfrac{1711}{2019}$ обратили в десятичную дробь, затем стерли первую цифру после запятой и обратили получившуюся десятичную дробь в обыкновенную. Какое число получилось?

Олимпиада «Ломоносов» 2011. В оригинале $\frac{1711}{2011}$. Приводится собственное решение. По «случайному» совпадению, 1711 - год рождения Ломоносова.

Будем решать задачу в общем виде. Пусть $s$ – положительное число, меньшее 1 (именно такое число нам дано). Представим это число в виде десятичной дроби: $$ s = \overline{0,a_1 a_2 а_3 \ldots},. $$

После вычеркивания первой цифры после запятой получаем число $t$: $$ t = \overline{0,a_2 a_3 \ldots}\,. $$

Заметим, что если начальное число $s$ увеличить в 10 раз (то есть сдвинуть запятую вправо на одну позицию), получим десятичную дробь $$ 10s = \overline{a_1,a_2 a_3 \ldots}\,, $$ дробная часть которой совпадает с десятичной дробью числа $t$. Таким образом $$ t = \{10s\} \label{eq:1.9.1}\tag{1.9.1}\,, $$где $\{\ldots\}$ – обозначение дробной части.

Для нахождения дробной части запишем $\frac{17110}{2019}$ в виде смешанной дроби: $\dfrac{17110}{2019} = 8\dfrac{958}{2019}$.

Ответ: $\dfrac{958}{2019}$.

Так как периодичность дроби нигде не использовалась, формула $\eqref{eq:1.9.1}$ применима также к непериодической дроби (то есть к иррациональному числу.)

Часть 2

2.1Указать множество чисел $n$, для которых $\lambda(n)=1$.

Вначале предположим, что $n$ не кратно 2 или 5. Тогда, согласно утверждению 4.1.1,  $n$ должно быть отличным от 1 делителем числа 9, так что $n$ равно 3 или 9. Легко проверить (хотя это не является необходимым), что действительно $\lambda(3) = \lambda(9) = 1$. Далее, из 4.4.5, следует, что $\lambda(n)=1$ для всякого $n$ вида $3\cdot2^p\cdot5^q$ или $9\cdot2^p\cdot5^q$, где $p$ и $q$ — целые неотрицательные числа, и наоборот, если $\lambda(n)=1$, то $n$ может быть представлено в одном из вышеуказанных видов.

Ответ: $n=2^p3^k5^q$, где k, p, q — целые числа, причем, $1\leqslant k \leqslant2$, $p \geqslant 0$, $q \geqslant 0$.

2.2Выведите формулу для  $\lambda(2^{n_1}\,3^{n_2}\,5^{n_3}\,7^{n_4}11^{n_5})$,  где  $n_i$ — целые неотрицательные числа.

Прежде всего, в силу утверждения 4.4.2, множители $2^{n_1}$  и  $5^{n_3}$ не влияют на длину периода, поэтому их можно игнорировать.

Далее, в 4.5 было показано, что $\lambda(7^n)=6 \cdot 7^{n-1}$, если $n \gt 0$. Так как множитель 7 может отсутствовать, следует доопределить эту формулу так, чтобы она равнялась 1 при $n=0$. Для этого введем функции sgn(знак числа) и max(наибольшее из чисел): $$ sgn(x) = \begin{cases} 1,\; \text{если}\; x \gt 0 \\ 0, \; \text{если}\; x \leqslant 0 \end{cases} $$ $$ max(x, y) = \begin{cases} x,\; \text{если}\; x \geqslant y \\ y, \; \text{если}\; x \lt y \end{cases} $$ Таким образом $\lambda(7^n) = 6^{sgn(n)} \; 7^{max(0, n-1)}$. Аналогично, $\lambda(3^n) = 3^{max(0, n-2)}$  и  $\lambda(11^n) = 2^{sgn(n)} \; 11^{max(0, n-1)}$.

Поскольку числа $3^{n_2}$, $7^{n_4}$,  и  взаимно простые, то, вследствие утверждения 4.5.1 (НОК — наименьшее общее кратное), $$ \begin{align} \lambda(2^{n_1}\,3^{n_2}\,5^{n_3}\,7^{n_4}11^{n_5}) & = \text{НОК}(3^{max(0,n_2-2)}, 6^{sgn(n_4)} \; 7^{max(0,n_4-1)}, 2^{sgn(n_5)} \; 11^{\max(0,n_5-1)}) \\ & = 2^{sgn(max(n_4,n_5))} \; 3^{max(n_2-2,sgn(n_4))} \; 7^{max(0,n_4-1)} \; 11^{max(0,n_5-1)}\;. \end{align} $$

Наконец, скорректируем формулу, чтобы она давала 0 для конечной дроби (то есть при отсутствии множителей 3,7,11): $$ \lambda(2^{n_1}\,3^{n_2}\,5^{n_3}\,7^{n_4}11^{n_5}) = 2^{sgn(max(n_4,n_5))} \; 3^{max(n_2-2,sgn(n_4))} \; 7^{max(0,n_4-1)} \; 11^{max(0,n_5-1)} \; sgn(max(n_2, n_4, n_5))\;, $$ где, разумеется, $max(n_2, n_4, n_5) = max(n_2, max(n_4, n_5))$ (ответ на возможные скептические замечания: $sgn(n_2 + n_4 + n_5)$ выглядит компактнее, однако менее интуитивно).

2.3Сформулируйте утверждения 4.1.1 и 4.4.2 для системы счисления с произвольным основанием $m \geqslant 2$.

Обобщение 4.1.1. Длина периода $m$-ичного представления несократимой дроби $\frac{a}{b}$, знаменатель которой взаимно прост с $m$, есть наименьшее из $n$, при котором число $m^{\,n}-1$ (число, представленное в $m$-ичной системе $n$ цифрами равными $m-1$) делится на $b$

Обобщение 4.4.2. Длина периода $m$-ичного представления несократимой дроби не изменится, если из разложения знаменателя на простые множители отбросить все делители $m$.

Для доказательства достаточно в рассуждениях заменить основание 10 основанием $m$.

2.4Рассмотрим $m$-ичное представление дроби $\frac{1}{m+1}$.
  а) Определите длину периода дроби.
  б) Найдите период дроби.
  в) Чему равна длина периода $m$-ичного представления дроби $\frac{1}{km+k}$, где $k$ — делитель $m$?

а) Очевидно $m$ и $m+1$ — взаимно простые числа. Ввиду рассмотренного в предыдущей задаче обобщения утверждения 4.1.1 длина периода $m$-ичного представления дроби $\frac{1}{m+1}$ есть наименьшее из $n$, при котором $c_n = m^n-1$ делится на $m+1$.

Пробуем $n=1$:  $c_1 = m-1 \lt m+1$, следовательно не может делиться на $m+1$.

Пробуем $n=2$:  $c_2 = m^2-1 = (m-1)(m+1)$ делится на $n+1$, следовательно $\lambda_m(m+1)=2$.

б) Из тождества $$ \frac{1}{m+1} = \frac{m-1}{m^2-1} $$ следует, что $\frac{1}{m+1} = 0,(0x)_m$, где $x$ – $m$-ичная цифра, соответствующая $m-1$. Например: $\frac{1}{11}=0,(09)$, $\frac{1}{9}=0,(07)_8$, $\frac{1}{13}=0,0Е_{12}$, ($Е$ - двенадцатеричное 11).

в) Из обобщения утверждения 4.4.2 предыдущей задачи следует, что $m$-ичные представления дробей $\frac{1}{k(m+1)}$ и $\frac{1}{m+1}$ имеют одинаковую длину периода, поэтому длина периода $m$-ичного представления дроби $\frac{1}{k(m+1)}$ также равна 2.

2.5Чему равно $m$-ичное представление дроби $\frac{1}{m^k-1}$, где $k$ — некоторое целое положительное число?

Согласно правилу перевода «чисто-периодической» $m$-ичной дроби в обыкновенную, получаем: $$ 0,(\underbrace{0 \dots 0}_{k-1\;\text{нулей}}1)_{m} = \frac{1}{m^k-1}\;, $$ таким образом $\dfrac{1}{m^k-1} = 0,(\underbrace{0 \dots 0}_{k-1\;\text{нулей}}1)_{m}$.

Другой подход. Применение формулы суммы членов бесконечно-убывающей геометрической прогрессии дает: $$ \begin{array}{l} 0,(\underbrace{0 \dots 0}_{k-1\;\text{нулей}}1)_{m} = \frac{1}{m^k} + \frac{1}{m^{2k}} + \frac{1}{m^{3k}} + \dots = \frac{\frac{1}{m^k}}{1-\frac{1}{m^k}} = \frac{1}{m^k-1} \end{array} $$

В частности, $\dfrac{1}{m-1} = 0,(1)_m$

2.6Пусть $p$—простое число, отличное от 2 и 5. Какие из следующих утверждений (в десятичной системе счисления) являются заведомо верными:
  а) Длина периода несократимой дроби  $\frac{m}{p}$  четна;
  б) Период несократимой дроби  $\frac{m}{p}$  кратен 9;
  в) Число  $\underbrace{11...1}_{p\;\text{единиц}}$  кратно $p$?

а) Неверно. Утверждение верно для полнопериодного простого $p$, где $\lambda(p)=\varphi(p)=p-1$, однако для других простых чисел длина периода может оказаться нечетной (хотя, разумеется, делителем $p-1$). Например, $\frac{1}{31}=0,(032258064516129)$ (длина периода 15),  $\frac{1}{37}=0,(027)$ (длина периода 3).

б) Верно, как частный случай утверждения 5.2.3, соответствующий $k=1$.

в) Верно, как частный случай утверждения 5.2.4, соответствующий $k=1$.

2.7Десятичное представление правильной дроби $\frac{m}{p}\quad$ является бесконечной периодической дробью, период которой состоит только из нулей и единиц, причем его длина меньше 10. Может $p$ быть простым числом?

Допустим $p$ – простое число. Так как десятичное представление является является бесконечной периодической дробью, то $m \gt 0$  и  $p$ отлично от 2 и 5. Кроме того, $\frac{m}{p}$ — правильная дробь, поэтому, $0 \lt m \lt p$, следовательно $m$ и $p$ – взаимно простые и дробь несократимая. Как было замечено в решении предыдущей задачи, из вышесказанного следует, что период дроби кратен 9, так что сумма цифр периода кратна 9.

С другой стороны, период десятичной состоит только из нулей и единиц, общее количество которых не превосходит 9. При этом сумма цифр периода кратна 9 лишь тогда, когда период содержит только нули или состоит из девяти единиц. В случае периода из одних нулей дробь не является бесконечной периодической, тогда как период из девяти единиц — это на самом деле период из одной единицы, соответствующий дроби $\frac{1}{9}$. Полученное противоречие показывает, что $p$ обязано быть составным числом.

2.8Среди правильных дробей с простым знаменателем, десятичное представление которых содержит каждую из цифр 1,3,4,5,6 найти дроби с наименьшей длиной периода.

Разумеется, дроби $\frac{1}{2}$ и $\frac{1}{5}$ не подходят, а если простой знаменатель отличен от 2 и 5, дробь является «чисто-периодической», с нулевой целой частью (ведь дробь правильная), так что заданные цифры могут появиться только в периоде. Заметим, что правильная дробь с простым знаменателем является несократимой, следовательно, согласно рассмотренного ранее ответу на вопрос 2.6б, ее период кратен 9.

Просуммируем заданные цифры: 1+3+4+5+6=19. Так как сумма не делится на 9, дробь требуемого свойства с периодом из 5 цифр найти не удастся. Поэтому увеличим период до 6 цифр, добавив цифру 8 для делимости на 9. В таком случае, согласно 4.1.1 знаменатель дроби должен быть делителем числа $10^6-1$, то есть содержаться среди простых множителей 999999.

Итак, разложим число 999999 на простые множители: $999999 = 3^3 \cdot 7\cdot 11 \cdot 13 \cdot 37$. Из этих множителей следует выбрать те, которые в качестве знаменателя дают длину периода 6. Знаменатели 3, 11, 37 встречались ранее и было замечено, что $\lambda(3)=1$,   $\lambda(11)=2$,   $\lambda(37)=3$ (впрочем, это нетрудно перепроверить).

В 5.1 было выяснено, что период правильных дробей со знаменателем 7 является циклической перестановкой цифр 1,4,2,8,5,7. Это исключает 7 из рассмотрения.

Таким образом, единственная надежда найти период из 6 цифр связана с несчастливым числом 13. Однако не будем суеверными. Разделив «уголком» 1 на 13, получаем 0,(076923) с остатками 10,9,12,3,4,1. Увы период содержит совсем другие цифры, но еще не все потеряно, так как длина периода составляет лишь половину от $\varphi(13)=12$. Например, число 2 не встречается среди остатков, поэтому дробь $\frac{2}{13}$ даст другие цифры в периоде. Получаем $\frac{2}{13}=0,(153846)$, остатки: 7,5,11,6,8,2. Теперь период содержит именно те цифры, которые мы ищем, так что в этот раз число 13 не подвело!

Чтобы найти все дроби, содержащие заданные цифры в периоде, следует делать циклические сдвиги в периоде, перемещая последнюю цифру в конец, при этом в числитель помещается очередной остаток. Вот что получаем: $$ \begin{array}{cc} \frac{2}{13} = 0,(153846); & \frac{7}{13} = 0,(538461); \\ \frac{5}{13} = 0,(384615); & \frac{11}{13} = 0,(846153); \\ \frac{6}{13} = 0,(461538); & \frac{8}{13} = 0,(615384). \end{array} $$

Наконец, чтобы ответ смотрелся аккуратно, расположим дроби в порядке возрастания: $$ \begin{array}{cc} \frac{2}{13} = 0,(153846); & \frac{5}{13} = 0,(384615); \\ \frac{6}{13} = 0,(461538); & \frac{7}{13} = 0,(538461); \\ \frac{8}{13} = 0,(615384); & \frac{11}{13} = 0,(846153). \end{array} $$

2.9Целое число записанное в $b^n$-ичной системе счисления можно перевести в $b$-ичную систему путем замены каждой $b^n$-ичной цифры соответствующим $b$-ичным представлением, при необходимости дополненным нулями до $n$-значного.
  a) Примени́м аналогичный метод к $b^n$-ичным дробям?
  b) Пусть длина периода $b^n$-ичной дроби равна $k$. Всегда ли длина периода соответствующей $b$-ичной дроби равна $nk$?

а) Примени́м с одной оговоркой: в результате этого период может не оказаться наименьшим. Попытаемся, например, перевести шестнадцатеричное представление дроби $\frac{1}{7}$ в двоичную систему счисления. Получаем $$ \frac{1}{7} = 0,(249)_{16} $$ $$ 2 = 0010_2, \quad 4 = 0100_2, \quad 9 = 1001_2 $$

Подставляя двоичные значения, получаем: $\frac{1}{7} = 0,(001001001001)_2$, что можно записать короче, как $0,(001)_2$, так что длина периода оказалась равной 3, а не 12, как ожидалось.

Если рассмотреть ту же дробь в восьмеричной системе, получим $\frac{1}{7}=0,(1)_8$, так что в этом случае период после перевода в двоичную систему не допускает упрощения.

б) Из вышесказанного следует, что длина периода полученной дроби является делителем $nk$, но не обязательно равна $nk$, так что утверждение в общем случае неверно.

2.10Докажите, что следующие правильные дроби с положительным знаменателем представимы в виде суммы двух аликвотных дробей с различными знаменателями:
  а) аликвотная дробь;
  б) дробь с числителем, равным 2;
  в) дробь с числителем, равным 4 и знаменателем, дающим при делении на 4 остаток, отличный от 1.
г) Найдите правильную дробь с числителем 4 и положительным знаменателем, не представимую в виде суммы двух аликвотных дробей.

а) Легко проверить, тождество $$ \frac{1}{m} \equiv \frac{1}{m+1} + \frac{1}{m(m+1)}\;, \label{eq:2.10.1}\tag{2.10.1} $$ дающее требуемое преставление.

б) Если знаменатель дроби — четное число, дробь можно сократить до аликвотной дроби, рассмотренной в а). Для нечетного знаменателя имеем: $$ \frac{2}{2m+1} \equiv \frac{1}{m+1} + \frac{1}{(m+1)(2m+1)}\;. $$

в) Если при делении на 4 знаменатель дает остаток 0 или 2, дробь можно сократить на 4 или 2, получая дробь, рассмотренную в одном из предыдущих пунктов. Осталось рассмотреть остаток 3, при котором: $$ \frac{4}{4m+3} \equiv \frac{1}{m+1} + \frac{1}{(m+1)(4m+3)}\;. $$

г) Докажем, что дробь $\frac{4}{5}$ не представима в виде суммы двух аликвотных дробей. Если $\frac{4}{5} = \frac{1}{a} + \frac{1}{b}$, где $a \leqslant b$, то $a \leqslant 2$, так как при $3 \leqslant a \leqslant b$ получаем $\frac{1}{a} + \frac{1}{b} \leqslant \frac{2}{3} \lt \frac{4}{5}$. С другой строны, $a \gt 1$, так как если $a=1$, то $\frac{1}{a} + \frac{1}{b} \gt 1 \gt \frac{4}{5}$. Таким образом, $a=2$, откуда $\frac{1}{b} = \frac{4}{5} - \frac{1}{2} = \frac{3}{10}$, что невозможно при целом $b$. Однако трех аликвотных дробей достаточно для $\frac{4}{5}$: $$ \frac{4}{5}\; = \; \frac{1}{2} + \frac{1}{4} + \frac{1}{20} \;=\; \frac{1}{2} + \frac{1}{5} + \frac{1}{10} $$

В этой связи нельзя не упомянуть о до сих пор не доказанной гипотезе Эрдёша-Штрауса (англ. Erdős–Straus conjecture), утверждаюшей, что для любого целого $n \geqslant 2$ дробь $\frac{4}{n}$ представима в виде суммы трех (не обязательно прaвильных и не обязательно различных) аликвотных дробей. Имеем: $$ \begin{array}{l} \frac{4}{2} = \frac{1}{1} + \frac{1}{2} + \frac{1}{2} \\ \frac{4}{3} = \frac{1}{2} + \frac{1}{2} + \frac{1}{3} \\ \frac{4}{4} = \frac{1}{3} + \frac{1}{3} + \frac{1}{3} \end{array} $$

Остальные дроби с числителем 4 являются правильными. Было доказано, что если знаменатель отличен от $4m+1$, такая дробь представима в виде суммы двух аликвотных дробей. Применив $\eqref{eq:2.10.1}$, получаем сумму трех аликвотных дробей. Докажите для знаменателя $4m+1$ — и войдете в историю! При этом не забудьте сослаться на эту статью. 😉

2.11Пусть $p_i$, $q_i$ — соответственно числитель и знаменатель $i$-го заголовка цепной дроби $[a_0;a_1, \dots a_{n-1}]$. Докажите, что
  $\dfrac{p_i}{p_{i-1}} = [a_i; a_{i-1}, \dots a_0]$  при  $0 \leqslant i \leqslant n-1$;
  $\dfrac{q_i}{q_{i-1}} = [a_i; a_{i-1}, \dots a_1]$  при  $1 \leqslant i \leqslant n-1$

Источники: «А.Я.Хинчин. Цепные дроби. 3-е изд. ГИФМЛ М. 1960, гл I § 2»,   "C.D.Olds Continued Fractions, Random House 1963, Problem Set 3, problem 7"

Применим метод математической индукции. База индукции: $$ \begin{array}{l} \dfrac{p_0}{p_{-1}} = \dfrac{a_0}{1} = a_0 \\ \dfrac{q_1}{q_0} = \dfrac{a_1}{1} = a_1\;, \end{array} $$ что согласуется с доказываемым утверждением.

Пусть утверждение верно для $i=k$. Применяя рекуррентные формулы, получаем: $$ \begin{array}{l} \dfrac{p_{k+1}}{p_k} = \dfrac{a_{k+1}\,p_k+q_{p-1}}{p_k} = a_{k+1} + \dfrac{p_{k-1}}{p_k}\\ \dfrac{q_{k+1}}{q_k} = \dfrac{a_{k+1}\,q_k+q_{k-1}}{q_k} = a_{k+1} + \dfrac{q_{k-1}}{q_k}\,. \end{array} $$

Так как, согласно индукционному предположению, $\dfrac{p_k}{p_{k-1}} = [a_k; a_{k-1} \dots a_0]$  и  $\dfrac{q_k}{q_{k-1}} = [a_k; a_{k-1} \dots a_1]$, то $$ \begin{array}{l} \dfrac{p_{k+1}}{p_k} = a_{k+1} + \dfrac{1}{[a_k, a_{k-1} \dots a_0]} = [a_{k+1}; a_k, \dots a_0]\\ \dfrac{q_{k+1}}{q_k} = a_{k+1} + \dfrac{1}{[a_k, a_{k-1} \dots a_1]} = [a_{k+1}; a_k, \dots a_1]\,, \end{array} $$ чем завершается индукционный переход.

2.12Положительные рациональные числа  $a$  и  $b$  записаны в виде десятичных дробей, у каждой из которых наименьший период состоит из 30 цифр. У десятичной записи числа  $a-b$  длина наименьшего периода равна 15. При каком наименьшем натуральном  $k$  длина наименьшего периода десятичной записи числа $a+kb$ может также оказаться равной 15?

40-я Всероссийская олимпиада школьников (заключительный этап), 2014

Подберем достаточно большое натуральное $m$ при котором знаменатели несократимых дробей, соответствующих  $a_1=10^ma$  и  $b_1=10^mb$  не содержат 2 и 5 в качестве простых множителей. Десятичные представления чисел  $a_1$  и  $b_1$  являются «чисто-периодическими», причем, согласно 4.4.1 наименьшие периоды дробей также равны 30. Знаменатели дробей  $a_1-b_1$  и  $a_1+kb_1$  являются делителями произведения знаменателей дробей  $a_1$  и  $b_1$,  следовательно, эти знаменатели также взаимно просты с 10, поэтому  $a_1-b_1$  и  $a_1+kb_1$  также представляются «чисто-периодическими дробями». Так как  $a_1 - b_1 = 10^m(a-b)$ , длина периода  $a_1-b_1$  также равна 15. Кроме того, поскольку $a_1 + kb_1 = 10^m(a + kb)$, длины периодов дробей $a_1 + kb_1$  и $a + kb$ одинаковы, поэтому всякое $k$, подходящее для $a_1 + kb_1$ подходит также для $a + kb$ и наоборот. Чтобы не иметь дело с индексами, будем предполагать, что  $a$ и  $b$  выражаются «чисто-периодическими» дробями.

Путь  $\lambda(a+kb)= \lambda(a-b) = 15. $ Согласно 4.1.1 $$ a-b = \frac{p}{10^{\,15}-1} \qquad a+kb = \frac{q}{10^{\,15}-1}, $$ где $p$ и $q$ — натуральные числа. Вычитая первое равенство из второго, получаем: $$ (k+1)b = \frac{q-p}{10^{\,15}-1} \label{eq:2.12.1}\tag{2.12.1} $$

С другой стороны, $\lambda(b)=30$, так что $$ b = \frac{r}{10^{\,30}-1}, \label{eq:2.12.2}\tag{2.12.2} $$ где $r$ — натуральное число, причем 30 нельзя заменить меньшим показателем степени.

Подставляя значение $b$ из $\eqref{eq:2.12.2}$  в  $\eqref{eq:2.12.1}$ и воспользуясь равенством $10^{\,30}-1 =(10^{\,15}-1)(10^{\,15}+1)$ получаем: $$ \frac{(k+1)r}{10^{15}+1} = q-p, $$ поэтому  $(k+1)r$  делится на $10^{15}+1$.

С другой стороны  $r$  не делится на $10^{\,15}+1$, так как если $r = (10^{\,15}+1)\,r_1$, то из $\eqref{eq:2.12.1}$ следует $$ b = \frac{(10^{\,15}+1)r_1}{(10^{\,15}-1)(10^{\,15}+1)} = \frac{r_1}{10^{\,15}-1}, $$ что противоречит минимальности периода 30, так что числа $k+1$ и $10^{15}+1$ обязаны иметь общий делитель, отличный от 1.

Итак, будем искать делители числа $10^{15}+1$, благо мы (в отличие от участников олимпиады) не ограничены во времени. Числа 2, 3, 5 не стоит даже и пробовать, так что 7 — это первая надежда. Делим: $1000000000000001 = 7 \cdot 142857142857143$. Разделилось!

Заметим, что если $k+1 = 7$, то $k=6$. Осталось подобрать $a$  и  $b$, такие, что $\lambda(a) = \lambda(b) = 30$, $\lambda(a-b) = \lambda(a+6b) = 15$. Не мудрствуя лукаво, положим $$ a - b = \dfrac{1}{10^{15}-1}; \qquad a + 6b = \dfrac{2}{10^{15}-1} \label{eq:2.12.3}\tag{2.12.3} $$ Очевидно, дроби в правой части несократимы, чем доказано $\lambda(a-b) = \lambda(a+6b) = 15$.

Из $\eqref{eq:2.12.3}$ несложно вычислить $a$  и  $b$: $$ a = \dfrac{8}{7(10^{15}-1)}; \qquad b = \dfrac{1}{7(10^{15}-1)} \label{eq:2.12.4}\tag{2.12.4} $$

Ввиду несократимости дробей в правой части $\eqref{eq:2.12.4}$, длины периода десятичных представлений $a$  и  $b$ больше 15. С другой стороны, как мы убедились, $10^{15}+1$ делится на 7, так что $а$  и  $b$ можно расширить до дроби со знаменателем $10^{30}-1$ умножив на 142857142857143. Это показывает, что 30 является одним из периодов десятичного представления $а$  и  $b$. Докажем минимальность периода 30.

Пусть $P$ длина некоторого периода десятичного представления, например, $a$. Тогда $P \gt 15$. При этом $a = \dfrac{M}{10^P - 1}$, так что ввиду $\eqref{eq:2.12.4}$, знаменатель $10^P - 1$ кратен $10^{15}-1$. Разделив $P$ на 15 с остатком, $$ P = 15Q + R \quad, \text{где} \; 0 \leqslant R \lt 15, $$ получаем: $$ M = \frac{10^P - 1}{10^{15}-1} = \frac{(10^{15})^Q\cdot10^R - 1}{10^{15}-1} = \frac{(10^{15})^Q-1}{10^{15}-1}\,10^R + \frac{10^R-1}{10^{15}-1} $$

Так как $M$   и   первое слагаемые — целые числа, целым должно быть и второе слагаемое $\dfrac{10^R-1}{10^{15}-1}$. Однако $R \lt 15$, так что числитель может разделиться на знаменатель только будучи нулем: $10^R-1=0$, откуда $R=0$. Таким образом $P$ кратно 15 и больше 15, следовательно $P \geqslant 30$.

Мы показали, что 30 - период десятичных представлений $a$  и  $b$, а кроме того, длина любого периода не меньше 30. Таким образом, действительно $\lambda(a) = \lambda(b) = 30$.

 

Описание Часть 1

Описание Часть 2

Условия задач

Решения задач