Олимпиадные задачи по теме «Индукция» для 10 класса - сложность 2 с решениями
Индукция
НазадНа доску последовательно выписываются числа <i>a</i><sub>1</sub> = 1, <i>a</i><sub>2</sub>, <i>a</i><sub>3</sub>, ... по следующим правилам: <i>a</i><sub><i>n</i>+1</sub> = <i>a<sub>n</sub></i> – 2, если число <i>a<sub>n</sub></i> – 2 – натуральное и еще не выписано на доску, в противном случае <i>a</i><sub><i>n</i>+1</sub> = <i>a<sub>n</sub></i> + 3. Докажите, что все квадраты натуральных чисел появятся в этой последовательности при прибавлении 3 к предыдущему числу.
Докажите неравенство <img align="absmiddle" src="/storage/problem-media/98473/problem_98473_img_2.gif"> при любых натуральных <i>n</i> и <i>k</i>.
Десятичные записи натуральных чисел выписаны подряд, начиная с единицы, до некоторого <i>n</i> включительно: 12345678910111213...(<i>n</i>). Существует ли такое <i>n</i>, что в этой записи все десять цифр встречаются одинаковое количество раз?
Рассматривается числовой треугольник: <div align="center"><img src="/storage/problem-media/98176/problem_98176_img_2.gif"></div>(первая строчка задана, а каждый элемент остальных строчек вычисляется как разность двух элементов, которые стоят над ним). В 1993-й строчке – один элемент. Найдите его.
Докажите, что при любом натуральном <i>n</i> найдётся ненулевой многочлен <i>P</i>(<i>x</i>) с коэффициентами, равными 0, –1, 1, степени не больше 2<sup><i>n</i></sup>, который делится на
(<i>x</i> – 1)<sup><i>n</i></sup>.
Двое играющих по очереди увеличивают натуральное число так, чтобы при каждом увеличении разность между новым и старым значениями числа была бы больше нуля, но меньше старого значения. Начальное значение числа равно 2. Выигравшим считается тот, в результате хода которого получится 1987. Кто выигрывает при правильной игре: начинающий или его партнёр?
Имеется много кубиков одинакового размера, раскрашенных в шесть цветов. При этом каждый кубик раскрашен во все шесть цветов, каждая грань – в какой-нибудь один свой цвет, но расположение цветов на разных кубиках может быть различным. Кубики выложены на стол, так что получился прямоугольник. Разрешается взять любой столбец этого прямоугольника, повернуть его вокруг длинной оси и положить на место. То же самое разрешается делать и со строками. Всегда ли можно с помощью таких операций добиться того, что все кубики будут смотреть вверх гранями одного и того же цвета?
Берутся всевозможные непустые подмножества из множества чисел 1, 2, 3, ..., <i>n</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 четвёрка).
Из натуральных чисел составляются последовательности, в которых каждое последующее число больше квадрата предыдущего, а последнее число в последовательности равно 1969 (последовательности могут иметь разную длину). Доказать, что различных последовательностей такого вида меньше чем 1969.
Остров<i>Толпыго</i>имеет форму многоугольника. На нём расположено несколько стран, каждая из которых имеет форму треугольника, причём каждые две граничащие страны имеют целую общую сторону (т.е. вершина одного треугольника не лежит на стороне другого). Доказать, что карту этого острова можно так раскрасить тремя красками, чтобы каждая страна была закрашена одним цветом и любые две соседние страны были закрашениы в разные цвета.
На окружности радиуса 1 отмечена точка<i>O</i>и из неё циркулем делается засечка вправо радиусом<i>l</i>. Из полученной точки<i>O</i><sub>1</sub>в ту же сторону тем же радиусом делается вторая засечка, и так делается 1968 раз. После этого окружность разрезается во всех 1968 засечках, и получается 1968 дуг. Сколько различных длин дуг может при этом получиться?
Разобьём все натуральные числа на группы так, чтобы в первой группе было одно число, во второй — два, в третьей — три и т.д. Можно ли это сделать таким образом, чтобы из суммы чисел в каждой группе нацело извлекался корень седьмой степени?
Проведём в выпуклом многоугольнике некоторые диагонали так, что никакие две из них не пересекаются (из одной вершины могут выходить несколько диагоналей). Доказать, что найдутся по крайней мере две вершины многоугольника, из которых не проведено ни одной диагонали.
Доказать, что любое натуральное число можно представить в виде суммы нескольких различных членов последовательности 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 href="http://www.problems.ru/view_problem_details_new.php?id=78240">задачу 3 для 7 класса</a>.
Доказать, что любая правильная дробь может быть представлена в виде (конечной) суммы обратных величин попарно различных целых чисел.
Дана последовательность $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, то такими операциями можно получить любое натуральное число.