Олимпиадные задачи по теме «Индукция» для 11 класса - сложность 2 с решениями
Индукция
НазадДокажите неравенство <img align="absmiddle" src="/storage/problem-media/98473/problem_98473_img_2.gif"> при любых натуральных <i>n</i> и <i>k</i>.
Имеется много кубиков одинакового размера, раскрашенных в шесть цветов. При этом каждый кубик раскрашен во все шесть цветов, каждая грань – в какой-нибудь один свой цвет, но расположение цветов на разных кубиках может быть различным. Кубики выложены на стол, так что получился прямоугольник. Разрешается взять любой столбец этого прямоугольника, повернуть его вокруг длинной оси и положить на место. То же самое разрешается делать и со строками. Всегда ли можно с помощью таких операций добиться того, что все кубики будут смотреть вверх гранями одного и того же цвета?
Какое из двух чисел больше: а) <img src="/storage/problem-media/79303/problem_79303_img_2.gif"> (<i>n</i> двоек) или <img src="/storage/problem-media/79303/problem_79303_img_3.gif"> (<i>n</i> − 1 тройка); б) <img src="/storage/problem-media/79303/problem_79303_img_3.gif"> (<i>n</i> троек) или <img src="/storage/problem-media/79303/problem_79303_img_4.gif"> (<i>n</i> − 1 четвёрка).
Колода перфокарт четырёх цветов разложена в один ряд. Если две перфокарты одного цвета лежат рядом или через одну, то можно выбрасывать ту из них, которая левее. Кроме того, можно подкладывать справа любое количество перфокарт из других колод. Доказать, что можно подкладывать и выбрасывать перфокарты таким образом, чтобы в конце концов их осталось только четыре.
По заданной последовательности положительных чисел <i>q</i><sub>1</sub>,..., <i>q<sub>n</sub></i>, ... строится последовательность многочленов следующим образом:
<i>f</i><sub>0</sub>(<i>x</i>) = 1,
<i>f</i><sub>1</sub>(<i>x</i>) = <i>x</i>,
...
<i>f</i><sub><i>n</i>+1</sub>(<i>x</i>) = (1 + <i>q<sub>n</sub></i>)<i>xf<sub>n</sub></i>(<i>x</i>) – <i>q<sub>n</sub>f</i><sub><i>n</i>–1</sub>(<i>x</i>).
Докажите, что все вещественные корни <i>n</i>-го мног...
Доказать, что любое натуральное число можно представить в виде суммы нескольких различных членов последовательности 1, 2, 3, 5, 8, 13, ...,<i>a</i><sub>n</sub>=<i>a</i><sub>n - 1</sub>+<i>a</i><sub>n - 2</sub>,....
<i>n</i> точек соединены отрезками так, что каждая точка с чем-нибудь соединена и нет таких двух точек, которые соединялись бы двумя разными путями.
Доказать, что общее число отрезков равно <i>n</i> – 1.
Дана последовательность чисел <i>F</i><sub>1</sub>, <i>F</i><sub>2</sub>, ...; <i>F</i><sub>1</sub> = <i>F</i><sub>2</sub> = 1 и <i>F</i><sub><i>n</i>+2</sub> = <i>F<sub>n</sub> + F</i><sub><i>n</i>+1</sub>. Доказать, что <i>F</i><sub>5<i>k</i></sub> делится на 5 при <i>k</i> = 1, 2, ... .
Дана последовательность $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, либо на [<sup><i>x</i></sup>/<sub>2</sub>].
Докажите, что если вначале написано число 1, то такими операциями можно получить любое натуральное число.
Сто медвежат нашли в лесу ягоды: самый младший успел схватить 1 ягоду, медвежонок постарше – 2 ягоды, следующий – 4 ягоды, и так далее, самому старшему досталось 2<sup>99</sup> ягод. Лиса предложила им поделить ягоды "по справедливости". Она может подойти к двум медвежатам и распределить их ягоды поровну между ними, а если при этом возникает лишняя ягода, то лиса её съедает. Такие действия она продолжает до тех пор, пока у всех медвежат не станет ягод поровну. Какое наибольшее количество ягод может съесть лиса?
Докажите, что любое натуральное число можно представить в виде 3<sup><i>u</i><sub>1</sub></sup>2<sup><i>v</i><sub>1</sub></sup> + 3<sup><i>u</i><sub>2</sub></sup>2<sup><i>v</i><sub>2</sub></sup> + ... + 3<sup><i>u<sub>k</sub></i></sup>2<sup><i>v<sub>k</sub></i></sup>, где <i>u</i><sub>1</sub> > <i>u</i><sub>2</sub> > ... > <i>u<sub>k</sub></i> ≥ 0 и 0 ≤ <i>v</i><sub>1</sub> < <i>v</i><sub>2</sub> < ... < <i>v<sub>k</sub&g...
Бессмертная блоха прыгает по целым точкам на числовой прямой, стартуя с точки 0. Длина первого прыжка равна 3, второго – 5, третьего – 9, и так далее (длина <i>k</i>-го прыжка равна 2<sup><i>k</i></sup> + 1). Направление прыжка (вправо или влево) блоха выбирает самостоятельно. Может ли так случиться, что блоха рано или поздно побывает в каждой натуральной точке (возможно, побывав в некоторых точках больше, чем по разу)?
Существует ли такое значение α, что все члены бесконечной последовательности cos α, cos 2α, ..., cos(2<i><sup>n</sup>α</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<sub>k,l</sub></i>(<i>x</i>) – производящая функция последовательности <i>P<sub>k,l</sub></i>(<i>n</i>) из задачи <a href="https://mirolimp.ru/tasks/161525">161525</a>: <i>f<sub>k,l</sub></i>(<i>x</i>) = <i>P<sub>k,l</sub></i>(0) + <i>xP<sub>k,l</sub></i>(1) + ... + <i>x<sup>kl</sup>P<sub>k,l</sub></i>(<i>kl</i>). а) Докажите равенства: <i>f<sub>k,l</sub></i>(<i>x</i>) = <i>f</i><sub><i>k</i>–1,<i>l</i></sub>(<i>x</i>) + <i>x<sup>k</sup>f...
Докажите, что для любого числа<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">.
Докажите равенство: <img align="absmiddle" src="/storage/problem-media/60581/problem_60581_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}}$(фи с
крышкой'') — сопряженное к нему.
Докажите следующие свойства чисел Фибоначчи: <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...