Олимпиадные задачи по теме «Индукция» для 2-6 класса
Индукция
НазадПоследовательности положительных чисел (<i>x<sub>n</sub></i>) и (<i>y<sub>n</sub></i>) удовлетворяют условиям <img align="absmiddle" src="/storage/problem-media/109842/problem_109842_img_2.gif"> при всех натуральных <i>n</i>. Докажите, что если все числа <i>x</i><sub>1</sub>, <i>x</i><sub>2</sub>, <i>y</i><sub>1</sub>, <i>y</i><sub>2</sub> больше 1, то <i>x<sub>n</sub> > y<sub>n</sub></i> при каком-нибудь натуральном <i>n</i>.
Найдите в последовательности 2, 6, 12, 20, 30, ... число, стоящее а) на 6-м; б) на 1994-м месте. Ответ объясните.
Любую ли сумму из целого числа рублей больше семи, можно уплатить без сдачи денежными купюрами по 3 и 5 рублей?
Любую ли сумму из целого числа рублей, больше семи, можно уплатить без сдачи денежными купюрами по 3 и 5 руб.? Почему?
В поселке 100 домов. Какое наибольшее число замкнутых не пересекающихся заборов можно построить, чтобы каждый забор огораживал хотя бы один дом и никакие два забора не огораживали бы одну и ту же совокупность домов?
В прямоугольнике 3×<i>n</i> стоят фишки трёх цветов, по <i>n</i> штук каждого цвета.
Доказать, что можно переставить фишки в каждой строке так, чтобы в каждом столбце были фишки всех цветов.
Доказать, что 2<sup>2<i>n</i>–1</sup> + 3<i>n</i> + 4 делится на 9 при любом <i>n</i>.
а) В графе есть эйлеров путь. Доказать, что граф связен и вершин с нечётной степенью в нём не больше двух.
б) Доказать обратное: если в связном графе вершин с нечётной степенью не больше двух, то в нём есть эйлеров путь.
В стране каждые два города соединены дорогой с односторонним движением. Доказать, что можно проехать по всем городам, побывав в каждом по одному разу (то есть что в полном ориентированном графе есть <i>гамильтонов путь</i>).
В выражении 123*...*9 звёздочки заменяют на минус или плюс.
a) Может ли получиться 0?
б) Может ли получиться 1?
в) Какие числа могут получиться?
Сумма положительных чисел <i>x</i><sub>1</sub>, <i>x</i><sub>2</sub>, ..., <i>x<sub>n</sub></i> равна ½. Докажите, что <img align="MIDDLE" src="/storage/problem-media/30908/problem_30908_img_2.gif">
Какое из чисел <img align="absMIDDLE" src="/storage/problem-media/30905/problem_30905_img_2.gif"> (10 двоек) или <img align="absMIDDLE" src="/storage/problem-media/30905/problem_30905_img_3.gif"> (9 троек) больше? А если троек не 9, а 8?
Докажите, что для любого натурального <i>n</i> выполняется неравенство 3<i><sup>n</sup> > n</i>·2<i><sup>n</sup></i>.
20 команд сыграли круговой турнир по волейболу.
Докажите, что команды можно занумеровать числами от 1 до 20 так, что 1-я команда выиграла у 2-й, 2-я – у 3-й, ..., 19-я – у 20-й.