Олимпиадные задачи из источника «глава 3. Алгоритм Евклида и основная теорема арифметики» - сложность 3 с решениями
глава 3. Алгоритм Евклида и основная теорема арифметики
НазадДокажите, что если квадратное уравнение с целыми коэффициентами имеет корень <i>u</i> = [<i>a</i>; <img width="25" height="36" align="MIDDLE" border="0" src="/storage/problem-media/60626/problem_60626_img_2.gif">], то вторым корнем будет число <img align="absmiddle" src="/storage/problem-media/60626/problem_60626_img_3.gif">
Докажите, что если положительная квадратичная иррациональность α = <img width="66" height="58" align="MIDDLE" border="0" src="/storage/problem-media/60625/problem_60625_img_2.gif"> разлагается в чисто периодическую цепную дробь, то сопряженная ей квадратичная иррациональность α' = <img width="66" height="58" align="MIDDLE" border="0" src="/storage/problem-media/60625/problem_60625_img_3.gif"> принадлежит интервалу (– 1, 0).
Докажите, что если квадратное уравнение с целыми коэффициентами имеет корень [<img width="26" height="36" align="MIDDLE" border="0" src="/storage/problem-media/60624/problem_60624_img_2.gif">], то вторым корнем служит число <img align="middle" src="/storage/problem-media/60624/problem_60624_img_3.gif">
Докажите, что при <i>k</i> ≥ 1 выполняется равенство: <img width="73" height="56" align="MIDDLE" border="0" src="/storage/problem-media/60622/problem_60622_img_2.gif"> = [<i>a<sup>F<sub>k</sub></sup></i>; <i>a</i><sup><i>F</i><sub><i>k</i>–1</sub></sup>, ..., <i>a</i><sup><i>F</i><sub>0</sub></sup>], где {<i>F<sub>k</sub></i>} – последовательность чисел Фибоначчи.
Докажите, что если <img align="MIDDLE" src="/storage/problem-media/60619/problem_60619_img_2.gif"> то <sup><i>p</i></sup>/<sub><i>q</i></sub> – подходящая дробь к числу α.
Докажите равенство: [<img width="76" height="59" align="MIDDLE" border="0" src="/storage/problem-media/60618/problem_60618_img_2.gif">] = <img width="199" height="58" align="MIDDLE" border="0" src="/storage/problem-media/60618/problem_60618_img_3.gif">.
Докажите, что значение любой периодической цепной дроби – квадратичная иррациональность.
Найдите наименьшее натуральное <i>n</i>, для которого существует такое <i>m</i>, что <img align="absmiddle" src="/storage/problem-media/60615/problem_60615_img_2.gif">
Найдите наименьшее натуральное <i>n</i>, для которого существует такое <i>m</i>, что <img align="absmiddle" src="/storage/problem-media/60614/problem_60614_img_2.gif">
Разложите в цепные дроби числа:
а) <img width="25" height="36" align="MIDDLE" border="0" src="/storage/problem-media/60613/problem_60613_img_2.gif">; б) <img width="25" height="36" align="MIDDLE" border="0" src="/storage/problem-media/60613/problem_60613_img_3.gif">; ½ + <img width="25" height="36" align="MIDDLE" border="0" src="/storage/problem-media/60613/problem_60613_img_4.gif">.
Вычислите следующие цепные дроби:
а) [5; (1, 2, 1, 10}]; б) [5; (1, 4, 1, 10}]; в) [2; (1, 1, 3}].
Наиболее точный календарь ввёл в Персии в 1079 году персидский астроном, математик и поэт Омар Альхайями. Восстановите этот календарный стиль, рассмотрев третью подходящую дробь [365; 4, 7, 1] к длительности астрономического года. За сколько лет в этом календаре накапливается ошибка в одни сутки?
Последовательности {<i>a<sub>k</sub></i>} и {<i>b<sub>k</sub></i>} строятся по следующему закону: <i>a</i><sub>1</sub> = 1, <img align="absmiddle" src="/storage/problem-media/60609/problem_60609_img_2.gif"> <i>a</i><sub><i>n</i>+1</sub> = min(<i>a<sub>n</sub>, b<sub>n</sub></i>), <i>b</i><sub><i>n</i>+1</sub> = |<i>b<sub>n</sub> – a<sub>n</sub></i>| (<i>n</i> ≥ 1).
а) Докажите, что <i>a<sub>n</sub></i> ≠ 0 и <i>a<sub>n</sub></i> стремится к 0 при <i>n</i> → ∞.
б)...
Докажите, что для любой бесконечной цепной дроби [<i>a</i><sub>0</sub>; <i>a</i><sub>1</sub>, ..., <i>a<sub>n</sub></i>, ...] существует предел её подходящих дробей – иррациональное число α. Объясните, почему если это число α разложить в бесконечную цепную дробь при помощи алгоритма задачи <a href="https://mirolimp.ru/tasks/160606">160606</a>, то получится бесконечная цепная дробь, равная исходной.
Докажите следующие свойства подходящих дробей:
а) <i>P<sub>k</sub>Q</i><sub><i>k</i>–2</sub> – <i>P</i><sub><i>k</i>–2</sub><i>Q<sub>k</sub></i> = (–1)<i><sup>k</sup>a<sub>k</sub></i> (<i>k</i> ≥ 2);
б) <img width="28" height="51" align="MIDDLE" border="0" src="/storage/problem-media/60602/problem_60602_img_2.gif"> – <img width="45" height="51" align="MIDDLE" border="0" src="/storage/problem-media/60602/problem_60602_img_3.gif"> = <img width="65" height="56" align="MIDDLE" border=&...
Пусть <i>a</i><sub>0</sub> – целое, <i>a</i><sub>1</sub>, ..., <i>a<sub>n</sub></i> – натуральные числа. Определим две последовательности
<i>P</i><sub>–1</sub> = 1, <i>P</i><sub>0</sub> = <i>a</i><sub>0</sub>, <i>P<sub>k</sub> = a<sub>k</sub>P</i><sub><i>k</i>–1</sub> + <i>P</i><sub><i>k</i>–2</sub> (1 ≤ <i>k ≤ n</i>); <i>Q</i><sub>–1</sub> = 0, <i>Q</i><sub>0</sub> = 1, <i>Q<sub>k</sub> = a<sub>k</sub>Q</i><sub><i>k</i>–1</sub&...
Для данного рационального числа <sup><i>a</i></sup>/<sub><i>b</i></sub> постройте электрическую цепь из единичных сопротивлений, общее сопротивление которой равнялось бы <sup><i>a</i></sup>/<sub><i>b</i></sub>. Как такую цепь можно получить при помощи разбиения прямоугольника <i>a</i>×<i>b</i> на квадраты из задачи <a href="https://mirolimp.ru/tasks/160598">160598</a>?
Пусть <i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>, ... – такая последовательность ненулевых чисел, что (<i>a<sub>m</sub>, a<sub>n</sub></i>) = <i>a</i><sub>(<i>m, n</i>)</sub> (<i>m, n</i> ≥ 1).Докажите, что все <i>обобщенные биномиальные коэффициенты</i> <img align="absMIDDLE" src="/storage/problem-media/60594/problem_60594_img_2.gif"> являются целыми числами.
Пусть число <i>m</i><sub>1</sub> в десятичной системе счисления записывается при помощи <i>n</i> цифр.
Докажите, что при любом <i>m</i><sub>0</sub> число шагов <i>k</i> в алгоритме Евклида для чисел <i>m</i><sub>0</sub> и <i>m</i><sub>1</sub> удовлетворяет неравенству <i>k</i> ≤ 5<i>n</i>.
Последовательность<i>чисел Люка</i> {<i>L</i><sub>0</sub>,<i>L</i><sub>1</sub>,<i>L</i><sub>2</sub>, ...} = {2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, ...} задается равенствами<i>L</i><sub>0</sub>=2,<i>L</i><sub>1</sub>=1,<i>L</i><sub>n</sub>=<i>L</i><sub>n-1</sub>+<i>L</i><sub>n-2</sub>при n>1. Выразите<i>L</i><sub>n</sub>в замкнутой форме через$\varphi$и$\widehat{\varphi}$.
<b>Определение</b>. Последовательность<i>чисел Люка</i> {<i>L</i><sub>0</sub>,<i>L</i><sub>1</sub>,<i>L</i><sub>2</sub>, ...} = {2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, ...} задается равенствами<i>L</i><sub>0</sub>=2,<i>L</i><sub>1</sub>=1,<i>L</i><sub>n</sub>=<i>L</i><sub>n-1</sub>+<i>L</i><sub>n-2</sub>при n>1. Докажите, что числа Люка связаны с числами Фибоначчи соотношениями: а)<i>L</i><sub>n</sub>=<i>F</i><sub>n - 1</sub>+<i>F</i><sub>n + 1</sub>; б)5 <i>F</i><sub>...
Решите в целых числах уравнение <i>x</i>φ<sup><i>n</i>+1</sup> + <i>y</i>φ<sup><i>n</i></sup>.
Число φ определено в задаче <a href="https://mirolimp.ru/tasks/160578">160578</a>.
<b>Фибоначчиева система счисления.</b>Докажите, что произвольное натуральное число<i>n</i>, не превосходящее<i>F</i><sub>m</sub>, единственным образом можно представит в виде<div align="CENTER"> <i>n</i> = $\displaystyle \sum\limits_{k=2}^{m}$<i>b</i><sub>k</sub><i>F</i><sub>k</sub>, </div>где все числа<i>b</i><sub>2</sub>, ...,<i>b</i><sub>m</sub>равны 0 либо 1, причем среди этих чисел нет двух единиц стоящих рядом, то есть<i>b</i><sub>k</sub><i>b</i><sub>k + 1</sub>= 0(2$\leqslant$<i>k</i>$\leqslant$<i>m</i>- 1). Для записи числа в фибоначчие...
В последовательности чисел Фибоначчи выбрано 8 чисел, идущих подряд. Докажите, что их сумма не является числом Фибоначчи.
Пусть первое число Фибоначчи, делящееся на <i>m</i>, есть <i>F<sub>k</sub></i>. Докажите, что <i>m | F<sub>n</sub></i> тогда и только тогда, когда <i>k | n</i>.