Олимпиадные задачи по теме «Индукция» для 6-7 класса

В классе каждый болтун дружит хотя бы с одним молчуном. При этом болтун молчит, если в кабинете находится нечетное число его друзей – молчунов. Докажите, что учитель может пригласить на факультатив не менее половины класса так, чтобы все болтуны молчали.

В компании из  2<i>n</i> + 1 человека для любых <i>n</i> человек найдётся отличный от них человек, знакомый с каждым из них.

Докажите, что в этой компании есть человек, знающий всех.

Среди 300 учеников одной математической школы некоторые путают лево и право, некоторые не путают, а некоторые делают все наоборот, чем им говорят. Первого сентября всех учеников выстроили в одну шеренгу (плечом к плечу) и скомандовали "нале-во!" По этой команде все одновременно повернулись на 90°, — кто налево, а кто направо. Ровно через секунду каждый, кто оказался лицом к лицу к соседу, понимает, что не прав, и поворачивается кругом (на 180°). Как долго это может продолжаться?

Существует ли конечное слово из букв русского алфавита, в котором нет двух соседних одинаковых подслов, но таковые появляются при приписывании (как справа, так и слева) любой буквы русского алфавита.Комментарий.<i>Словом</i>мы называем любую последовательность букв русского алфавита, не обязательно осмысленную,<i>подсловом</i>называется любой фрагмент слова. Например, АБВШГАБ - слово, а АБВ, Ш, ШГАБ - его подслова.

Банкир узнал, что среди одинаковых на вид монет одна — фальшивая (более легкая). Он попросил эксперта определить эту монету с помощью чашечных весов без гирь, причем потребовал, чтобы каждая монета участвовала во взвешиваниях не более двух раз. Какое наибольшее число монет может быть у банкира, чтобы эксперт заведомо смог выделить фальшивую за<i>n</i>взвешиваний?

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

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

На некотором поле шахматной доски стоит фишка. Двое по очереди переставляют фишку, при этом на каждом ходу, начиная со второго, расстояние, на которое она перемещается, должно быть строго больше, чем на предыдущем ходу. Проигравшим считается тот, кто не может сделать очередной ход. Кто выигрывает при правильной игре? (Фишка ставится всегда точно в центр каждого поля.)

Каждая клетка шахматной доски закрашена в один из цветов – синий или красный. Докажите, что клетки одного из цветов обладают тем свойством, что их может обойти шахматный ферзь (на клетках этого цвета ферзь может побывать не один раз, на клетки другого цвета он не ставится, но может через них перепрыгивать).

На доске написаны числа 1, 2, 3, …, 20. Разрешается стереть любые два числа<var>a</var>и<var>b</var>и заменить их суммой<var>ab</var>+<var>a</var>+<var>b</var>. Какое число может получиться после 19 таких операций?

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

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

Для всякого ли натурального <i>n</i> можно расставить первые <i>n</i> натуральных чисел в таком порядке, чтобы ни для каких двух чисел их полусумма не равнялась ни одному из чисел, расположенных между ними?

Дано<i>n</i>фишек нескольких цветов, причём фишек каждого цвета не<nobr>более <i>n</i>/2.</nobr>Докажите, что их можно расставить на окружности так, чтобы никакие две фишки одинакового цвета не стояли рядом.

<i>n</i> человек не знакомы между собой. Нужно так познакомить друг с другом некоторых из них, чтобы ни у каких трёх людей не оказалось одинакового числа знакомых. Докажите, что это можно сделать при любом <i>n</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>

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

В таблице размерами <i>m×n</i> расставлены числа – в каждой клетке по числу. В каждом столбце подчеркнуто <i>k</i> наибольших чисел  (<i>k ≤ m</i>),  в каждой строке – <i>l</i> наибольших чисел  (<i>l ≤ n</i>).  Докажите, что по крайней мере <i>kl</i> чисел подчёркнуты дважды.

<img src="/storage/problem-media/73554/problem_73554_img_2.gif" width="172" height="69" vspace="10" hspace="20" align="right">В бесконечной цепочке нервных клеток каждая может находиться в одном из двух состояний: «покой» и «возбуждение». Если в данный момент клетка возбудилась, то она посылает сигнал, который через единицу времени (скажем, через одну миллисекунду) доходит до обеих соседних с ней клеток. Каждая клетка возбуждается в том и только в том случае, если к ней приходит сигнал от одной из соседних клеток; если сигналы приходят одновременно с двух сторон, то они погашаются, и клетка не возбуждается. Например, если в начальной момент времени<nobr><i>t</i> = 0</nobr>возбудить три соседние клетки...

Имеется кучка из 100 камней. Двое играют в следующую игру. Первый игрок забирает 1 камень, потом второй может забрать 1 или 2 камня, потом первый может забрать 1, 2 или 3 камня, затем второй 1, 2, 3 или 4 камня, и так далее. Выигрывает тот, кто забирает последний камень. Кто может выиграть, как бы ни играл соперник?

Вычислите произведение   <img align="absmiddle" src="/storage/problem-media/60313/problem_60313_img_2.gif">

Докажите тождество: 1 + 3 + 5 +...+ (2<i>n</i>– 1) =<i>n</i>².

Число<i>x</i>таково, что число<i>x</i>+${\dfrac{1}{x}}$ — целое. Докажите, что при любом натуральном<i>n</i>число<i>x</i>ⁿ+${\frac{1}{x^n}}$также является целым.

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

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