Олимпиадные задачи из источника «параграф 4. О том, как размножаются кролики» для 6-8 класса - сложность 2 с решениями
параграф 4. О том, как размножаются кролики
НазадРассмотрим алгоритм Евклида из задачи <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>n</i>? Например, если <i>n</i> = 4, то таких последовательностей пять: 1111, 112, 121, 211, 22.
Докажите по индукции формулу Бине:<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</i><sub><i>n</i>–1</sub> и <i>F<sub>n</sub></i> (<i>n</i> ≥ 1) взаимно просты.
Докажите, что при<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>?
Чему равны числа Фибоначчи с отрицательными номерами<i>F</i><sub>-1</sub>,<i>F</i><sub>-2</sub>, ...,<i>F</i><sub>-n</sub>,...?
Некоторый алфавит состоит из 6 букв, которые для передачи по телеграфу кодированы так:<div align="CENTER"> <sup> . </sup> - <sup> . . </sup> - - <sup> . </sup> - - <sup> . </sup> </div>При передаче одного слова не сделали промежутков, отделяющих букву от буквы, так что получилась сплошная цепочка из точек и тире, содержащая 12 знаков. Сколькими способами можно прочитать переданное слово?
<b>О том, как прыгают кузнечики.</b>Предположим, что имеется лента, разбитая на клетки и уходящая вправо до бесконечности. На первой клетке этой ленты сидит кузнечик. Из любой клетки кузнечик может перепрыгнуть либо на одну, либо на две клетки вправо. Сколькими способами кузнечик может добраться до<i>n</i>-ой от начала ленты клетки?
Некто приобрел пару кроликов и поместил их в огороженный со всех сторон загон. Сколько кроликов будет через год, если считать, что каждый месяц пара дает в качестве приплода новую пару кроликов, которые со второго месяца жизни также начинают приносить приплод?