Олимпиадные задачи из источника «параграф 4. О том, как размножаются кролики» - сложность 3 с решениями
параграф 4. О том, как размножаются кролики
НазадПусть <i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>, ... – такая последовательность ненулевых чисел, что (<i>a<sub>m</sub>, a<sub>n</sub></i>) = <i>a</i><sub>(<i>m, n</i>)</sub> (<i>m, n</i> ≥ 1).Докажите, что все <i>обобщенные биномиальные коэффициенты</i> <img align="absMIDDLE" src="/storage/problem-media/60594/problem_60594_img_2.gif"> являются целыми числами.
Пусть число <i>m</i><sub>1</sub> в десятичной системе счисления записывается при помощи <i>n</i> цифр.
Докажите, что при любом <i>m</i><sub>0</sub> число шагов <i>k</i> в алгоритме Евклида для чисел <i>m</i><sub>0</sub> и <i>m</i><sub>1</sub> удовлетворяет неравенству <i>k</i> ≤ 5<i>n</i>.
Последовательность<i>чисел Люка</i> {<i>L</i><sub>0</sub>,<i>L</i><sub>1</sub>,<i>L</i><sub>2</sub>, ...} = {2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, ...} задается равенствами<i>L</i><sub>0</sub>=2,<i>L</i><sub>1</sub>=1,<i>L</i><sub>n</sub>=<i>L</i><sub>n-1</sub>+<i>L</i><sub>n-2</sub>при n>1. Выразите<i>L</i><sub>n</sub>в замкнутой форме через$\varphi$и$\widehat{\varphi}$.
<b>Определение</b>. Последовательность<i>чисел Люка</i> {<i>L</i><sub>0</sub>,<i>L</i><sub>1</sub>,<i>L</i><sub>2</sub>, ...} = {2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, ...} задается равенствами<i>L</i><sub>0</sub>=2,<i>L</i><sub>1</sub>=1,<i>L</i><sub>n</sub>=<i>L</i><sub>n-1</sub>+<i>L</i><sub>n-2</sub>при n>1. Докажите, что числа Люка связаны с числами Фибоначчи соотношениями: а)<i>L</i><sub>n</sub>=<i>F</i><sub>n - 1</sub>+<i>F</i><sub>n + 1</sub>; б)5 <i>F</i><sub>...
Решите в целых числах уравнение <i>x</i>φ<sup><i>n</i>+1</sup> + <i>y</i>φ<sup><i>n</i></sup>.
Число φ определено в задаче <a href="https://mirolimp.ru/tasks/160578">160578</a>.
<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). Для записи числа в фибоначчие...
В последовательности чисел Фибоначчи выбрано 8 чисел, идущих подряд. Докажите, что их сумма не является числом Фибоначчи.
Пусть первое число Фибоначчи, делящееся на <i>m</i>, есть <i>F<sub>k</sub></i>. Докажите, что <i>m | F<sub>n</sub></i> тогда и только тогда, когда <i>k | n</i>.
Докажите, что для любого натурального <i>m</i> существует число Фибоначчи <i>F<sub>n</sub></i> (<i>n</i> ≥ 1), кратное <i>m</i>.
Докажите справедливость следующих утверждений:
а) 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>F</i><sub>n + 2</sub><sup>4</sup>-<i>F</i><sub>n</sub><i>F</i><sub>n + 1</sub><i>F</i><sub>n + 3</sub><i>F</i><sub>n + 4</sub>.