Олимпиадные задачи по теме «Индукция» - сложность 2 с решениями

Дана последовательность чисел <i>F</i>₁, <i>F</i>₂, ...;  <i>F</i>₁ = <i>F</i>₂ = 1  и   <i>F</i>_<i>n</i>+2 = <i>F_n + F</i>_<i>n</i>+1.  Доказать, что <i>F</i>_5<i>k</i> делится на 5 при  <i>k</i> = 1, 2, ... .

См.<a href="http://www.problems.ru/view_problem_details_new.php?id=78240">задачу 3 для 7 класса</a>.

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

2<i>m</i>-значное число назовём справедливым, если его чётные разряды содержат столько же чётных цифр, сколько и нечётные. Докажите, что в любом (2<i>m</i>+1)-значном числе можно вычеркнуть одну из цифр так, чтобы полученное 2<i>m</i>-значное число было справедливым. Пример для числа 12345 показан на рисунке. <div align="center"><img src="/storage/problem-media/73628/problem_73628_img_2.gif"></div>

Дана последовательность $a_n = n!\mkern2mu(n^2-2025n+1)$ для всех натуральных $n$. Найдите сумму первых $2025$ членов этой последовательности.

Имеется кучка из 100 камней. Двое играют в следующую игру. Первый игрок забирает 1 камень, потом второй может забрать 1 или 2 камня, потом первый может забрать 1, 2 или 3 камня, затем второй 1, 2, 3 или 4 камня, и так далее. Выигрывает тот, кто забирает последний камень. Кто может выиграть, как бы ни играл соперник?

Пусть $n$ – натуральное число. Назовём последовательность $a_1, a_2, ..., a_n$ <i>интересной</i>, если для каждого  $i$ = 1, 2, ..., $n$  верно одно из равенств  $a_i = i$  или  $a_i = i$ + 1.  Назовём интересную последовательность <i>чётной</i>, если сумма её членов чётна, и <i>нечётной</i> – иначе. Для каждой нечётной интересной последовательности нашли произведение её чисел и записали его на первый листок. Для каждой чётной – сделали то же самое и записали на второй листок. На каком листке сумма чисел больше и на сколько? (Дайте ответ в зависимости от $n$.)

Хозяйка испекла квадратный торт и отрезала от него несколько кусков. Первый разрез проведён параллельно стороне исходного квадрата от края до края. Следующий разрез проведён в оставшейся части от края до края перпендикулярно предыдущему разрезу, далее аналогично (сколько-то раз). Все отрезанные куски имеют равную площадь. Может ли оставшаяся часть торта быть квадратом?

Любое число $x$, написанное на доске, разрешается заменить либо на  3$x$ + 1,  либо на  [^<i>x</i>/₂].

Докажите, что если вначале написано число 1, то такими операциями можно получить любое натуральное число.

Три богатыря сражаются со Змеем Горынычем. Илья Муромец каждым своим ударом отрубает половину всех голов и еще одну, Добрыня Никитич — треть всех голов и еще две, а Алёша Попович — четверть всех голов и еще три. Богатыри бьют по одному, в том порядке, в котором считают нужным. Если ни один богатырь не может ударить из-за того, что число голов получится нецелым, то Змей съедает богатырей. Смогут ли богатыри отрубить все головы $20^{20}$-головому Змею?

Сто медвежат нашли в лесу ягоды: самый младший успел схватить 1 ягоду, медвежонок постарше – 2 ягоды, следующий – 4 ягоды, и так далее, самому старшему досталось 2⁹⁹ ягод. Лиса предложила им поделить ягоды "по справедливости". Она может подойти к двум медвежатам и распределить их ягоды поровну между ними, а если при этом возникает лишняя ягода, то лиса её съедает. Такие действия она продолжает до тех пор, пока у всех медвежат не станет ягод поровну. Какое наибольшее количество ягод может съесть лиса?

Сто медвежат нашли в лесу ягоды: самый младший успел схватить 1 ягоду, медвежонок постарше – 2 ягоды, следующий – 4 ягоды, и так далее, самому старшему досталось 2⁹⁹ ягод. Лиса предложила им поделить ягоды "по справедливости". Она может подойти к двум медвежатам и распределить их ягоды поровну между ними, а если при этом возникает лишняя ягода, то лиса её съедает. Такие действия она продолжает до тех пор, пока у всех медвежат не станет ягод поровну. Какое наименьшее количество ягод может оставить медвежатам лиса?

Докажите, что любое натуральное число можно представить в виде  3^<i>u</i>₁2^<i>v</i>₁ + 3^<i>u</i>₂2^<i>v</i>₂ + ... + 3^<i>u_k</i>2^<i>v_k</i>,  где  <i>u</i>₁ > <i>u</i>₂ > ... > <i>u_k</i> ≥ 0  и  0 ≤ <i>v</i>₁ < <i>v</i>₂ < ... < <i>v<sub>k</sub&g...

Бессмертная блоха прыгает по целым точкам на числовой прямой, стартуя с точки 0. Длина первого прыжка равна 3, второго – 5, третьего – 9, и так далее (длина <i>k</i>-го прыжка равна  2^<i>k</i> + 1).  Направление прыжка (вправо или влево) блоха выбирает самостоятельно. Может ли так случиться, что блоха рано или поздно побывает в каждой натуральной точке (возможно, побывав в некоторых точках больше, чем по разу)?

Существует ли такое значение α, что все члены бесконечной последовательности cos α, cos 2α, ..., cos(2<i>ⁿα</i>), ... принимают отрицательные значения?

Ученик Коля Васин при помощи метода математической индукции смог доказать, что в любом табуне все лошади одной масти. Если есть только одна лошадь, то она своей масти, так что база индукции верна. Для индуктивного перехода предположим, что есть<i>n</i>лошадей (с номерами от 1 до<i>n</i>). По индуктивному предположению лошади с номерами от 1 до<i>n</i>- 1 одинаковой масти. Аналогично лошади с номерами от 2 до<i>n</i>также имеют одинаковую масть. Но лошади с номерами от 2 до<i>n</i>- 1 не могут менять свою масть в зависимости от того как они сгруппированы — это лошади, а не хамелеоны. Поэтому все<i>n</i>лошадей должны быть одинаковой масти. Есть ли ошибка в этом рассуждении, и если есть, то какая?

  Пусть <i>f_k,l</i>(<i>x</i>) – производящая функция последовательности <i>P_k,l</i>(<i>n</i>) из задачи <a href="https://mirolimp.ru/tasks/161525">161525</a>:   <i>f_k,l</i>(<i>x</i>) = <i>P_k,l</i>(0) + <i>xP_k,l</i>(1) + ... + <i>x^klP_k,l</i>(<i>kl</i>).   а) Докажите равенства:  <i>f_k,l</i>(<i>x</i>) = <i>f</i>_{<i>k</i>–1,<i>l</i>}(<i>x</i>) + <i>x^kf...

Докажите, что для любого числа<i>p</i>> 2 найдется такое число$\beta$, что<div align="CENTER"> $\displaystyle \underbrace{\sqrt{2+\sqrt{2+\ldots+\sqrt{2+ \sqrt{2+p}}}}}{n~\mbox{\scriptsize {радикалов}}}^{},$ = $\displaystyle \beta^{2^n}{}$ - $\displaystyle \beta^{-2^n}_{}$. </div>

Лягушка прыгает по вершинам треугольника <i>ABC</i>, перемещаясь каждый раз в одну из соседних вершин.

Сколькими способами она может попасть из <i>A</i> в <i>A</i> за <i>n</i> прыжков?

Докажите, что для любых натуральных <i>m</i> и <i>n</i> хотя бы одно из чисел  <img width="32" height="33" align="MIDDLE" border="0" src="/storage/problem-media/61396/problem_61396_img_2.gif">,  <img width="34" height="33" align="MIDDLE" border="0" src="/storage/problem-media/61396/problem_61396_img_3.gif">  не больше  <img width="26" height="36" align="MIDDLE" border="0" src="/storage/problem-media/61396/problem_61396_img_4.gif">.

Докажите, что каждое целое число<i>A</i>представимо в виде<div align="CENTER"> <i>A</i> = <i>a</i>₀ + 2<i>a</i>₁ + 2²<i>a</i>₂ +...+ 2ⁿ<i>a</i>_n, </div>где каждое из чисел<i>a</i>_k= 0, 1 или -1 и<i>a</i>_k<i>a</i>_{k + 1}= 0 для всех0$\leqslant$<i>k</i>$\leqslant$<i>n</i>- 1, причем такое представление единственно.

Докажите равенство:   <img align="absmiddle" src="/storage/problem-media/60581/problem_60581_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}}$(фи с крышкой'') — сопряженное к нему.

Докажите следующие свойства чисел Фибоначчи: <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>?