Олимпиадные задачи из источника «глава 3. Алгоритм Евклида и основная теорема арифметики» - сложность 2 с решениями
глава 3. Алгоритм Евклида и основная теорема арифметики
НазадДоказать, что остаток от деления простого числа на 30 – простое число или единица.
Даны два натуральных числа <i>m</i> и <i>n</i>. Выписываются все различные делители числа <i>m</i> – числа <i>a, b, ..., k</i> – и все различные делители числа <i>n</i> – числа <i>s, t, ..., z</i>. (Само число и 1 тоже включаются в число делителей.) Оказалось, что <i>a + b + ... + k = s + t + ... + z</i> и <sup>1</sup>/<sub><i>a</i></sub> + <sup>1</sup>/<sub><i>b</i></sub> + ... + <sup>1</sup>/<sub><i>k</i></sub> = <sup>1</sup>/<sub><i>s</i></sub> + <sup>1</sup>/<sub><i>t</i></sub> + ... + <sup>1</sup>/<sub>&l...
Доказать: число делителей <i>n</i> не превосходит 2<img width="27" height="33" align="MIDDLE" border="0" src="/storage/problem-media/78208/problem_78208_img_2.gif">.
а) Докажите, что положительный корень квадратного уравнения <i>bx</i>² – <i>abx – a</i> = 0, где <i>a</i> и <i>b</i> – различные натуральные числа, разлагается в чисто периодическую цепную дробь с длиной периода, равной 2.
б) Верно ли обратное утверждение?
Докажите, что если <sup><i>P<sub>n</sub></i></sup>/<sub><i>Q<sub>n</sub></i></sub> (<i>n</i> ≥ 1) – подходящая дробь к числу α, то имеет место по крайней мере одно из неравенств <img align="absmiddle" src="/storage/problem-media/60620/problem_60620_img_2.gif"> или <img align="absmiddle" src="/storage/problem-media/60620/problem_60620_img_3.gif"> Получите отсюда <i>теорему Валена</i>: для любого α найдётся бесконечно много таких дробей <sup><i>p</i></sup>/<sub><i>q</i></sub>, что |α – <sup><i>p</i></sup>/<sub><i>q</i></sub>| < <sup&g...
Найдите рациональное число, которое отличается от числа
а) α = <img width="25" height="36" align="MIDDLE" border="0" src="/storage/problem-media/60617/problem_60617_img_2.gif">; б) α = 2 + <img width="25" height="36" align="MIDDLE" border="0" src="/storage/problem-media/60617/problem_60617_img_3.gif">; в) α = 3 + <img width="25" height="36" align="MIDDLE" border="0" src="/storage/problem-media/60617/problem_60617_img_4.gif"> не более чем на 0,0001.
Из астрономии известно, что год имеет 365,2420... = [365; 4, 7, 1, 3,...] так называемых "календарных суток". В Юлианском стиле каждый четвёртый год – високосный, то есть состоит из 366 дней. За сколько лет при таком календаре накапливается ошибка в одни сутки? На сколько дней отстает Юлианский календарь за 1000 лет? И вообще, почему он отстает, если юлианский год длиннее астрономического?
Предположим, что число α задано бесконечной цепной дробью α = [<i>a</i><sub>0</sub>; <i>a</i><sub>1</sub>, ..., <i>a<sub>n</sub></i>, ...]. Докажите, что <img align="absMIDDLE" src="/storage/problem-media/60608/problem_60608_img_2.gif"> где <i>Q<sub>k</sub></i> – знаменатели подходящих дробей.
Докажите, что любое иррациональное число α допускает представление α = [<i>a</i><sub>0</sub>; <i>a</i><sub>1</sub>, ..., <i>a</i><sub><i>n</i>–1</sub>, α<sub><i>n</i></sub>], где <i>a</i><sub>0</sub> – целое, <i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>, ..., <i>a</i><sub><i>n</i>–1</sub> – натуральные, α<sub><i>n</i></sub> > 1 – иррациональное действительное. Отсюда следует, что каждому иррациональному действительному числу можно поставить в соответствие бесконечную цепную дробь.
<b>Григорианский календарь</b>. Обыкновенный год содержит 365 дней, високосный – 366. <i>n</i>-й год, номер которого не делится на 100, является високосным тогда и только тогда, когда <i>n</i> кратно 4. <i>n</i>-й год, где <i>n</i> кратно 100, является високосным тогда и только тогда, когда <i>n</i> кратно 400. Так, например, 1996 и 2000 годы високосные, а 1997 и 1900 – нет. Эти правила были установлены папой Григорием XIII. До сих пор мы имели ввиду <i>гражданский</i> год, число дней которого должно быть целым. <i>Астрономическим</i> же годом называется период времени, за который Земля совершает полный оборот вокруг Солнца. Считая, что <i>григорианский</i> год полностью согласован с...
Разлагая число <sup><i>a</i></sup>/<sub><i>b</i></sub> в непрерывную дробь, решите в целых числах уравнения <i>ax – by</i> = 1, если
a) <i>a</i> = 101, <i>b</i> = 13; б) <i>a</i> = 79, <i>b</i> = 19.
Пусть числа <i>a</i> и <i>b</i> определены равенством <sup><i>a</i></sup>/<sub><i>b</i></sub> = [<i>a</i><sub>0</sub>; <i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>, ..., <i>a<sub>n</sub></i>]. Докажите, что уравнение <i>ax – by</i> = 1 c неизвестными <i>x</i> и <i>y</i> имеет решением одну из пар (<i>Q</i><sub><i>n</i>–1</sub>, <i>P</i><sub><i>n</i>–1</sub>) или (– <i>Q</i><sub><i>n</i>–1</sub>, – <i>P</i><sub><i>n</i>–1</sub>), где <sup&...
Для каждого натурального <i>n</i> приведите пример прямоугольника, который разрезался бы ровно на <i>n</i> квадратов, среди которых должно быть не более двух одинаковых.
Работу алгоритма Евклида (см. задачу <a href="https://mirolimp.ru/tasks/160488">160488</a>) можно представить следующим образом. В прямоугольник размерами <i>m</i><sub>0</sub>×<i>m</i><sub>1</sub> (<i>m</i><sub>1</sub> ≤ <i>m</i><sub>0</sub>) укладываем <i>a</i><sub>0</sub> квадратов размера <i>m</i><sub>1</sub>×<i>m</i><sub>1</sub>, в оставшийся прямоугольник размерами <i>m</i><sub>1</sub>×<i>m</i><sub>2</sub> (<i>m</i><sub>2</sub> ≤ <i>m</i><sub>1</sub>) укладываем <i>a</i><sub>1...
Как связано разложение рационального числа в цепную дробь с алгоритмом Евклида?
Пусть <img align="absMIDDLE" src="/storage/problem-media/60596/problem_60596_img_2.gif"> Чему равны <i>P<sub>n</sub></i> и <i>Q<sub>n</sub></i>?
<div align="CENTER"> <table cellpadding="3"> <tr><td align="CENTER"> </td> <td align="CENTER"> </td> <td align="CENTER"> </td> <td align="CENTER"> </td> <td align="CENTER"> </td> <td align="CENTER"> </td> <td align="CENTER"> </td> <td align="CENTER">1</td> <td align="CENTER"> </td> <td align="CENTER"> </td> <td align="CENTER"> </td> <td align="CENTER"> </td> <td align="CENTER"> </td> <td align="CENTER"> </td> <td align="CENTER"> </...
Рассмотрим алгоритм Евклида из задачи <a href="https://mirolimp.ru/tasks/160488">160488</a>, состоящий из <i>k</i> шагов.
Докажите, что начальные числа <i>m</i><sub>0</sub> и <i>m</i><sub>1</sub> должны удовлетворять неравенствам <i>m</i><sub>1</sub> ≥ <i>F</i><sub><i>k</i>+1</sub>, <i>m</i><sub>0</sub> ≥ <i>F</i><sub><i>k</i>+2</sub>.
а) Докажите, что в последовательности чисел Фибоначчи при <i>m</i> ≥ 2 встречается не менее четырёх и не более пяти <i>m</i>-значных чисел.
б) Докажите, что число <i>F</i><sub>5<i>n</i>+2</sub> (<i>n</i> ≥ 0) содержит в своей десятичной записи не менее <i>n</i> + 1 цифры.
В вершинах правильных многоугольников записываются числа 1 и 2. Сколько существует таких многоугольников, что сумма чисел, стоящих в вершинах, равна<i>n</i>(<i>n</i>$\geqslant$3)? Две расстановки чисел, которые можно совместить поворотом, не отождествляются.
Сколько существует последовательностей из единиц и двоек, сумма всех элементов которых равна <i>n</i>? Например, если <i>n</i> = 4, то таких последовательностей пять: 1111, 112, 121, 211, 22.
Вычислите сумму: <img align="absmiddle" src="/storage/problem-media/60582/problem_60582_img_2.gif">
Докажите равенство: <img align="absmiddle" src="/storage/problem-media/60581/problem_60581_img_2.gif">
(Сумма, стоящая в левой части, может быть интерпретирована, как сумма элементов треугольника Паскаля, стоящих в одной диагонали.)
Докажите, что число Фибоначчи <i>F</i><sub>n</sub> совпадает с ближайшим целым числом к <img width="29" height="50" align="MIDDLE" border="0" src="/storage/problem-media/60580/problem_60580_img_2.gif">, то есть <i>F<sub>n</sub></i> = <img width="14" height="54" align="MIDDLE" border="0" src="/storage/problem-media/60580/problem_60580_img_3.gif"><img width="29" height="50" align="MIDDLE" border="0" src="/storage/problem-media/60580/problem_60580_img_2.gif"> + <img width="16" height="49" align="MIDDLE" border="0" src="/storage/pr...
Докажите следующий вариант <i>формулы Бине</i>: <img align="absmiddle" src="/storage/problem-media/60579/problem_60579_img_2.gif">