Олимпиадные задачи из источника «параграф 4. О том, как размножаются кролики» для 8 класса
параграф 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}}$(фи с
крышкой'') — сопряженное к нему.
<b>Фибоначчиева система счисления.</b>Докажите, что произвольное натуральное число<i>n</i>, не превосходящее<i>F</i><sub>m</sub>, единственным образом можно представит в виде<div align="CENTER"> <i>n</i> = $\displaystyle \sum\limits_{k=2}^{m}$<i>b</i><sub>k</sub><i>F</i><sub>k</sub>, </div>где все числа<i>b</i><sub>2</sub>, ...,<i>b</i><sub>m</sub>равны 0 либо 1, причем среди этих чисел нет двух единиц стоящих рядом, то есть<i>b</i><sub>k</sub><i>b</i><sub>k + 1</sub>= 0(2$\leqslant$<i>k</i>$\leqslant$<i>m</i>- 1). Для записи числа в фибоначчие...
Рассмотрим множество последовательностей длины<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) взаимно просты.
Докажите справедливость следующих утверждений:
а) 2 | <i>F<sub>n</sub></i> ⇔ 3 | <i>n</i>;
б) 3 | <i>F<sub>n</sub></i> ⇔ 4 | <i>n</i>;
в) 4 | <i>F<sub>n</sub></i> ⇔ 6 | <i>n</i>;
г) <i>F<sub>m</sub></i> | <i>F<sub>n</sub></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><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>-ой от начала ленты клетки?
Некто приобрел пару кроликов и поместил их в огороженный со всех сторон загон. Сколько кроликов будет через год, если считать, что каждый месяц пара дает в качестве приплода новую пару кроликов, которые со второго месяца жизни также начинают приносить приплод?