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

<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>₀ и <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  цифры.

В вершинах правильных многоугольников записываются числа 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>_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}}$(фи с крышкой'') — сопряженное к нему.

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

Докажите равенство  (<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)  взаимно просты.

Вычислите сумму<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>

Докажите равенства а)<i>F</i>_{2n + 1}=<i>F</i>_n²+<i>F</i>_{n + 1}²;         б)<i>F</i>_{n + 1}<i>F</i>_{n + 2}-<i>F</i>_n<i>F</i>_{n + 3}= (- 1)^{n + 1}; в)<i>F</i>_3n=<i>F</i>_n³+<i>F</i>_{n + 1}³-<i>F</i>_{n - 1}³.

Докажите, что при<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>-ой от начала ленты клетки?

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