Олимпиадные задачи по теме «Индукция» для 8 класса - сложность 2 с решениями
Индукция
НазадПетя умеет на любом отрезке отмечать точки, которые делят этот отрезок пополам или в отношении <i>n</i> : (<i>n</i> + 1), где <i>n</i> – любое натуральное число. Петя утверждает, что этого достаточно, чтобы на любом отрезке отметить точку, которая делит его в любом заданном рациональном отношении. Прав ли он?
На доску последовательно выписываются числа <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 к предыдущему числу.
Любую ли сумму из целого числа рублей больше семи, можно уплатить без сдачи денежными купюрами по 3 и 5 рублей?
Десятичные записи натуральных чисел выписаны подряд, начиная с единицы, до некоторого <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>. Для каждого подмножества берётся величина, обратная к произведению всех его чисел. Найти сумму всех таких обратных величин.
На доске написаны числа 1, 2, 3, …, 20. Разрешается стереть любые два числа<var>a</var>и<var>b</var>и заменить их суммой<var>ab</var>+<var>a</var>+<var>b</var>. Какое число может получиться после 19 таких операций?
Дано число, имеющее 13 разрядов. Доказать, что одну из его цифр можно вычеркнуть так, что в полученном числе количество семёрок на чётных местах будет равно количеству семёрок на нечётных местах.
Какое из двух чисел больше: а) <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 четвёрка).
Какое из двух чисел больше: а) <img src="/storage/problem-media/79299/problem_79299_img_2.gif"> (100 двоек) или <img src="/storage/problem-media/79299/problem_79299_img_3.gif"> (99 троек); б) <img src="/storage/problem-media/79299/problem_79299_img_3.gif"> (100 троек) или <img src="/storage/problem-media/79299/problem_79299_img_4.gif"> (99 четвёрок).
Из натуральных чисел составляются последовательности, в которых каждое последующее число больше квадрата предыдущего, а последнее число в последовательности равно 1969 (последовательности могут иметь разную длину). Доказать, что различных последовательностей такого вида меньше чем 1969.
На окружности радиуса 1 отмечена точка<i>O</i>и из неё циркулем делается засечка вправо радиусом<i>l</i>. Из полученной точки<i>O</i><sub>1</sub>в ту же сторону тем же радиусом делается вторая засечка, и так делается 1968 раз. После этого окружность разрезается во всех 1968 засечках, и получается 1968 дуг. Сколько различных длин дуг может при этом получиться?
Проведём в выпуклом многоугольнике некоторые диагонали так, что никакие две из них не пересекаются (из одной вершины могут выходить несколько диагоналей). Доказать, что найдутся по крайней мере две вершины многоугольника, из которых не проведено ни одной диагонали.
<i>a, b, p</i> – любые целые числа. Доказать, что найдутся такие взаимно простые <i>k, l</i>, что <i>ak + bl</i> делится на <i>p</i>.
Доказать, что любая правильная дробь может быть представлена в виде (конечной) суммы обратных величин попарно различных целых чисел.
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 камня, и так далее. Выигрывает тот, кто забирает последний камень. Кто может выиграть, как бы ни играл соперник?
Хозяйка испекла квадратный торт и отрезала от него несколько кусков. Первый разрез проведён параллельно стороне исходного квадрата от края до края. Следующий разрез проведён в оставшейся части от края до края перпендикулярно предыдущему разрезу, далее аналогично (сколько-то раз). Все отрезанные куски имеют равную площадь. Может ли оставшаяся часть торта быть квадратом?
Любое число $x$, написанное на доске, разрешается заменить либо на 3$x$ + 1, либо на [<sup><i>x</i></sup>/<sub>2</sub>].
Докажите, что если вначале написано число 1, то такими операциями можно получить любое натуральное число.
Три богатыря сражаются со Змеем Горынычем. Илья Муромец каждым своим ударом отрубает половину всех голов и еще одну, Добрыня Никитич — треть всех голов и еще две, а Алёша Попович — четверть всех голов и еще три. Богатыри бьют по одному, в том порядке, в котором считают нужным. Если ни один богатырь не может ударить из-за того, что число голов получится нецелым, то Змей съедает богатырей. Смогут ли богатыри отрубить все головы $20^{20}$-головому Змею?
Сто медвежат нашли в лесу ягоды: самый младший успел схватить 1 ягоду, медвежонок постарше – 2 ягоды, следующий – 4 ягоды, и так далее, самому старшему досталось 2<sup>99</sup> ягод. Лиса предложила им поделить ягоды "по справедливости". Она может подойти к двум медвежатам и распределить их ягоды поровну между ними, а если при этом возникает лишняя ягода, то лиса её съедает. Такие действия она продолжает до тех пор, пока у всех медвежат не станет ягод поровну. Какое наибольшее количество ягод может съесть лиса?
Сто медвежат нашли в лесу ягоды: самый младший успел схватить 1 ягоду, медвежонок постарше – 2 ягоды, следующий – 4 ягоды, и так далее, самому старшему досталось 2<sup>99</sup> ягод. Лиса предложила им поделить ягоды "по справедливости". Она может подойти к двум медвежатам и распределить их ягоды поровну между ними, а если при этом возникает лишняя ягода, то лиса её съедает. Такие действия она продолжает до тех пор, пока у всех медвежат не станет ягод поровну. Какое наименьшее количество ягод может оставить медвежатам лиса?