Олимпиадные задачи из источника «параграф 4. О том, как размножаются кролики» - сложность 2-4 с решениями

Пусть <i>a</i>₁, <i>a</i>₂, ... – такая последовательность ненулевых чисел, что  (<i>a_m, a_n</i>) = <i>a</i>_{(<i>m, n</i>)}  (<i>m, n</i> ≥ 1).Докажите, что все <i>обобщенные биномиальные коэффициенты</i>   <img align="absMIDDLE" src="/storage/problem-media/60594/problem_60594_img_2.gif">   являются целыми числами.

<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"> </...

Пусть число <i>m</i>₁ в десятичной системе счисления записывается при помощи <i>n</i> цифр.

Докажите, что при любом <i>m</i>₀ число шагов <i>k</i> в алгоритме Евклида для чисел <i>m</i>₀ и <i>m</i>₁ удовлетворяет неравенству  <i>k</i> ≤ 5<i>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>m</i> ≥ 2  встречается не менее четырёх и не более пяти <i>m</i>-значных чисел.

б) Докажите, что число <i>F</i>_5<i>n</i>+2  (<i>n</i> ≥ 0)  содержит в своей десятичной записи не менее  <i>n</i> + 1  цифры.

Решите в целых числах уравнения:   а)  <i>x</i>² – <i>xy – y</i>² = 1;   б)  <i>x</i>² – <i>xy – y</i>² = –1.

Последовательность<i>чисел Люка</i> {<i>L</i>₀,<i>L</i>₁,<i>L</i>₂, ...} = {2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, ...} задается равенствами<i>L</i>₀=2,<i>L</i>₁=1,<i>L</i>_n=<i>L</i>_n-1+<i>L</i>_n-2при n>1. Выразите<i>L</i>_nв замкнутой форме через$\varphi$и$\widehat{\varphi}$.

В вершинах правильных многоугольников записываются числа 1 и 2. Сколько существует таких многоугольников, что сумма чисел, стоящих в вершинах, равна<i>n</i>(<i>n</i>$\geqslant$3)? Две расстановки чисел, которые можно совместить поворотом, не отождествляются.

<b>Определение</b>. Последовательность<i>чисел Люка</i> {<i>L</i>₀,<i>L</i>₁,<i>L</i>₂, ...} = {2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, ...} задается равенствами<i>L</i>₀=2,<i>L</i>₁=1,<i>L</i>_n=<i>L</i>_n-1+<i>L</i>_n-2при n>1. Докажите, что числа Люка связаны с числами Фибоначчи соотношениями: а)<i>L</i>_n=<i>F</i>_{n - 1}+<i>F</i>_{n + 1}; б)5 <i>F</i><sub>...

Решите в целых числах уравнение   <i>x</i>φ^<i>n</i>+1 + <i>y</i>φ^<i>n</i>.

Число φ определено в задаче <a href="https://mirolimp.ru/tasks/160578">160578</a>.

Сколько существует последовательностей из единиц и двоек, сумма всех элементов которых равна <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>_n совпадает с ближайшим целым числом к  <img width="29" height="50" align="MIDDLE" border="0" src="/storage/problem-media/60580/problem_60580_img_2.gif">,  то есть  <i>F_n</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">

Докажите по индукции формулу Бине:<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>.

В последовательности чисел Фибоначчи выбрано 8 чисел, идущих подряд. Докажите, что их сумма не является числом Фибоначчи.

Докажите равенство  (<i>F_n, F_m</i>) = <i>F</i>_{(<i>m, n</i>)}.

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

Пусть первое число Фибоначчи, делящееся на <i>m</i>, есть <i>F_k</i>. Докажите, что  <i>m | F_n</i>  тогда и только тогда, когда  <i>k | n</i>.

Докажите, что для любого натурального <i>m</i> существует число Фибоначчи <i>F_n</i>  (<i>n</i> ≥ 1),  кратное <i>m</i>.

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

  а)  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.

Вычислите сумму<div align="CENTER"> $\displaystyle {\frac{1}{1\cdot2}}$ + $\displaystyle {\frac{2}{1\cdot3}}$ +...+ $\displaystyle {\frac{F_{n}}{F_{n-1}\cdot F_{n+1}}}$. </div>