Олимпиадные задачи из источника «глава 3. Алгоритм Евклида и основная теорема арифметики» для 2-8 класса

Доказать, что остаток от деления простого числа на 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>  и  ¹/_<i>a</i> + ¹/_<i>b</i> + ... + ¹/_<i>k</i> = ¹/_<i>s</i> + ¹/_<i>t</i> + ... + ¹/<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">.

<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> год полностью согласован с...

Работу алгоритма Евклида (см. задачу <a href="https://mirolimp.ru/tasks/160488">160488</a>) можно представить следующим образом. В прямоугольник размерами  <i>m</i>₀×<i>m</i>₁  (<i>m</i>₁ ≤ <i>m</i>₀)  укладываем <i>a</i>₀ квадратов размера   <i>m</i>₁×<i>m</i>₁,  в оставшийся прямоугольник размерами  <i>m</i>₁×<i>m</i>₂  (<i>m</i>₂ ≤ <i>m</i>₁)  укладываем <i>a</i><sub>1...

Как связано разложение рационального числа в цепную дробь с алгоритмом Евклида?

Пусть   <img align="absMIDDLE" src="/storage/problem-media/60596/problem_60596_img_2.gif">   Чему равны <i>P_n</i> и <i>Q_n</i>?

Разложите в цепные дроби числа ¹⁴⁷/₁₃ и ¹²⁹/₁₁₁.

Рассмотрим алгоритм Евклида из задачи <a href="https://mirolimp.ru/tasks/160488">160488</a>, состоящий из <i>k</i> шагов.

Докажите, что начальные числа <i>m</i>₀ и <i>m</i>₁ должны удовлетворять неравенствам  <i>m</i>₁ ≥ <i>F</i>_<i>k</i>+1,  <i>m</i>₀ ≥ <i>F</i>_<i>k</i>+2.

Сколько существует последовательностей из единиц и двоек, сумма всех элементов которых равна <i>n</i>? Например, если  <i>n</i> = 4,  то таких последовательностей пять: 1111,  112,  121,  211,  22.

Докажите по индукции формулу Бине:<div align="CENTER"> <i>F</i>_n = $\displaystyle {\dfrac{\varphi^n-\widehat{\varphi}^{n}}{\sqrt5}}$, </div>где$\varphi$=${\dfrac{1+\sqrt5}{2}}$— золотое сечение'' или число Фидия, а$\widehat{\varphi}$=${\dfrac{1-\sqrt5}{2}}$(фи с крышкой'') — сопряженное к нему.

<b>Фибоначчиева система счисления.</b>Докажите, что произвольное натуральное число<i>n</i>, не превосходящее<i>F</i>_m, единственным образом можно представит в виде<div align="CENTER"> <i>n</i> = $\displaystyle \sum\limits_{k=2}^{m}$<i>b</i>_k<i>F</i>_k, </div>где все числа<i>b</i>₂, ...,<i>b</i>_mравны 0 либо 1, причем среди этих чисел нет двух единиц стоящих рядом, то есть<i>b</i>_k<i>b</i>_{k + 1}= 0(2$\leqslant$<i>k</i>$\leqslant$<i>m</i>- 1). Для записи числа в фибоначчие...

Рассмотрим множество последовательностей длины<i>n</i>, состоящих из 0 и 1, в которых не бывает двух 1 стоящих рядом. Докажите, что количество таких последовательностей равно<i>F</i>_{n + 2}. Найдите взаимно-однозначное соответствие между такими последовательностями и маршрутами кузнечика из задачи <a href="https://mirolimp.ru/tasks/160561">3.109</a>.

Докажите, что два соседних числа Фибоначчи <i>F</i>_<i>n</i>–1 и <i>F_n</i>  (<i>n</i> ≥ 1)  взаимно просты.

Докажите справедливость следующих утверждений:

  а)  2 | <i>F_n</i>   ⇔   3 | <i>n</i>;

  б)  3 | <i>F_n</i>   ⇔   4 | <i>n</i>;

  в)  4 | <i>F_n</i>   ⇔   6 | <i>n</i>;

  г)  <i>F_m</i> | <i>F_n</i>   ⇔   <i>m | n</i>  при  <i>m</i> > 2.

Докажите, что при<i>n</i>$\geqslant$1 и<i>m</i>$\geqslant$0 выполняется равенство<div align="CENTER"> <i>F</i>_{n + m} = <i>F</i>_{n - 1}<i>F</i>_m + <i>F</i>_n<i>F</i>_{m + 1}. </div> Попробуйте доказать его двумя способами: при помощи метода математической индукции и при помощи интерпретации чисел Фибоначчи из задачи <a href="https://mirolimp.ru/tasks/160561">3.109</a>. Докажите также, что тождество Кассини (см. задачу<a href="https://mirolimp.ru/tasks/160564">3.112</a>) является частным случаем этого равенства.

Докажите следующие свойства чисел Фибоначчи: <table> <tr><td align="LEFT">а) <i>F</i>₁ + <i>F</i>₂ +...+ <i>F</i>_n = <i>F</i>_{n + 2} - 1;</td> <td align="LEFT">в) <i>F</i>₂ + <i>F</i>₄ +...+ <i>F</i>_2n = <i>F</i>_{2n + 1} - 1;</td> </tr> <tr><td align="LEFT">б) <i>F</i>₁ + <i>F</i>₃ +...+ <i>F</i>_{2n - 1} = <i>F</i><sub&g...

<b> Тождество Кассини.</b>Докажите равенство<div align="CENTER"> <i>F</i>_{n + 1}<i>F</i>_{n - 1} - <i>F</i>_n² = (- 1)ⁿ        (<i>n</i> > 0). </div> Будет ли тождество Кассини справедливо для всех целых<i>n</i>?

Чему равны числа Фибоначчи с отрицательными номерами<i>F</i>_-1,<i>F</i>_-2, ...,<i>F</i>_-n,...?

Некоторый алфавит состоит из 6 букв, которые для передачи по телеграфу кодированы так:<div align="CENTER"> ^.         -         ^{. .}         - -         ^. -          -  ^. </div>При передаче одного слова не сделали промежутков, отделяющих букву от буквы, так что получилась сплошная цепочка из точек и тире, содержащая 12 знаков. Сколькими способами можно прочитать переданное слово?

<b>О том, как прыгают кузнечики.</b>Предположим, что имеется лента, разбитая на клетки и уходящая вправо до бесконечности. На первой клетке этой ленты сидит кузнечик. Из любой клетки кузнечик может перепрыгнуть либо на одну, либо на две клетки вправо. Сколькими способами кузнечик может добраться до<i>n</i>-ой от начала ленты клетки?

Некто приобрел пару кроликов и поместил их в огороженный со всех сторон загон. Сколько кроликов будет через год, если считать, что каждый месяц пара дает в качестве приплода новую пару кроликов, которые со второго месяца жизни также начинают приносить приплод?

Докажите, что число  <img width="100" height="53" align="MIDDLE" border="0" src="/storage/problem-media/60558/problem_60558_img_2.gif">  (<i>m</i>, <i>n</i> ≥ 0)  целое.

Докажите, что число <i>p</i> входит в разложение <i>n</i>! с показателем, не превосходящим   <img align="absMIDDLE" border="0" src="/storage/problem-media/60554/problem_60554_img_2.gif">

Число <i>n</i>! разложено в произведение простых чисел:   <img align="absMIDDLE" src="/storage/problem-media/60553/problem_60553_img_2.gif">   Докажите равенство   <img align="absMIDDLE" src="/storage/problem-media/60553/problem_60553_img_3.gif">