Олимпиадные задачи из источника «параграф 4. О том, как размножаются кролики» для 10 класса - сложность 2 с решениями
параграф 4. О том, как размножаются кролики
Назад<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">
Докажите по индукции формулу Бине:<div align="CENTER">
<i>F</i><sub>n</sub> = $\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><sub>n + 2</sub>. Найдите взаимно-однозначное соответствие между такими последовательностями и маршрутами кузнечика из задачи <a href="https://mirolimp.ru/tasks/160561">3.109</a>.
Докажите равенство (<i>F<sub>n</sub>, F<sub>m</sub></i>) = <i>F</i><sub>(<i>m, n</i>)</sub>.
Докажите, что два соседних числа Фибоначчи <i>F</i><sub><i>n</i>–1</sub> и <i>F<sub>n</sub></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><sub>2n + 1</sub>=<i>F</i><sub>n</sub><sup>2</sup>+<i>F</i><sub>n + 1</sub><sup>2</sup>; б)<i>F</i><sub>n + 1</sub><i>F</i><sub>n + 2</sub>-<i>F</i><sub>n</sub><i>F</i><sub>n + 3</sub>= (- 1)<sup>n + 1</sup>; в)<i>F</i><sub>3n</sub>=<i>F</i><sub>n</sub><sup>3</sup>+<i>F</i><sub>n + 1</sub><sup>3</sup>-<i>F</i><sub>n - 1</sub><sup>3</sup>.
Докажите, что при<i>n</i>$\geqslant$1 и<i>m</i>$\geqslant$0 выполняется равенство<div align="CENTER"> <i>F</i><sub>n + m</sub> = <i>F</i><sub>n - 1</sub><i>F</i><sub>m</sub> + <i>F</i><sub>n</sub><i>F</i><sub>m + 1</sub>. </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><sub>1</sub> + <i>F</i><sub>2</sub> +...+ <i>F</i><sub>n</sub> = <i>F</i><sub>n + 2</sub> - 1;</td> <td align="LEFT">в) <i>F</i><sub>2</sub> + <i>F</i><sub>4</sub> +...+ <i>F</i><sub>2n</sub> = <i>F</i><sub>2n + 1</sub> - 1;</td> </tr> <tr><td align="LEFT">б) <i>F</i><sub>1</sub> + <i>F</i><sub>3</sub> +...+ <i>F</i><sub>2n - 1</sub> = <i>F</i><sub&g...
<b> Тождество Кассини.</b>Докажите равенство<div align="CENTER"> <i>F</i><sub>n + 1</sub><i>F</i><sub>n - 1</sub> - <i>F</i><sub>n</sub><sup>2</sup> = (- 1)<sup>n</sup> (<i>n</i> > 0). </div> Будет ли тождество Кассини справедливо для всех целых<i>n</i>?