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

Петя умеет на любом отрезке отмечать точки, которые делят этот отрезок пополам или в отношении  <i>n</i> : (<i>n</i> + 1),  где <i>n</i> – любое натуральное число. Петя утверждает, что этого достаточно, чтобы на любом отрезке отметить точку, которая делит его в любом заданном рациональном отношении. Прав ли он?

На доску последовательно выписываются числа  <i>a</i>₁ = 1,  <i>a</i>₂, <i>a</i>₃, ... по следующим правилам: <i>a</i>_<i>n</i>+1 = <i>a_n</i> – 2,  если число  <i>a_n</i> – 2  – натуральное и еще не выписано на доску, в противном случае  <i>a</i>_<i>n</i>+1 = <i>a_n</i> + 3.  Докажите, что все квадраты натуральных чисел появятся в этой последовательности при прибавлении 3 к предыдущему числу.

Найдите в последовательности 2, 6, 12, 20, 30, ... число, стоящее а) на 6-м; б) на 1994-м месте. Ответ объясните.

Любую ли сумму из целого числа рублей больше семи, можно уплатить без сдачи денежными купюрами по 3 и 5 рублей?

Докажите неравенство   <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^<i>n</i>, который делится на

(<i>x</i> – 1)^<i>n</i>.

Двое играющих по очереди увеличивают натуральное число так, чтобы при каждом увеличении разность между новым и старым значениями числа была бы больше нуля, но меньше старого значения. Начальное значение числа равно 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 таких операций?

Любую ли сумму из целого числа рублей, больше семи, можно уплатить без сдачи денежными купюрами по 3 и 5 руб.? Почему?

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

Дано число, имеющее 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.

Колода перфокарт четырёх цветов разложена в один ряд. Если две перфокарты одного цвета лежат рядом или через одну, то можно выбрасывать ту из них, которая левее. Кроме того, можно подкладывать справа любое количество перфокарт из других колод. Доказать, что можно подкладывать и выбрасывать перфокарты таким образом, чтобы в конце концов их осталось только четыре.

Остров<i>Толпыго</i>имеет форму многоугольника. На нём расположено несколько стран, каждая из которых имеет форму треугольника, причём каждые две граничащие страны имеют целую общую сторону (т.е. вершина одного треугольника не лежит на стороне другого). Доказать, что карту этого острова можно так раскрасить тремя красками, чтобы каждая страна была закрашена одним цветом и любые две соседние страны были закрашениы в разные цвета.

На окружности радиуса 1 отмечена точка<i>O</i>и из неё циркулем делается засечка вправо радиусом<i>l</i>. Из полученной точки<i>O</i>₁в ту же сторону тем же радиусом делается вторая засечка, и так делается 1968 раз. После этого окружность разрезается во всех 1968 засечках, и получается 1968 дуг. Сколько различных длин дуг может при этом получиться?

Разобьём все натуральные числа на группы так, чтобы в первой группе было одно число, во второй — два, в третьей — три и т.д. Можно ли это сделать таким образом, чтобы из суммы чисел в каждой группе нацело извлекался корень седьмой степени?

По заданной последовательности положительных чисел  <i>q</i>₁,..., <i>q_n</i>, ...  строится последовательность многочленов следующим образом:

    <i>f</i>₀(<i>x</i>) = 1,

    <i>f</i>₁(<i>x</i>) = <i>x</i>,

      ...

    <i>f</i>_<i>n</i>+1(<i>x</i>) = (1 + <i>q_n</i>)<i>xf_n</i>(<i>x</i>) – <i>q_nf</i>_<i>n</i>–1(<i>x</i>).

Докажите, что все вещественные корни <i>n</i>-го мног...

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

Доказать, что любое натуральное число можно представить в виде суммы нескольких различных членов последовательности 1, 2, 3, 5, 8, 13, ...,<i>a</i>_n=<i>a</i>_{n - 1}+<i>a</i>_{n - 2},....