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

а) В футбольном турнире в один круг участвовало 75 команд. За победу в матче команда получала 3 очка, за ничью 1 очко, за поражение 0 очков. Известно, что каждые две команды набрали различное количество очков. Найдите наименьшую возможную разность очков у команд, занявших первое и последнее места.б) Тот же вопрос для <i>n</i> команд.

На доске нарисован выпуклый 2011-угольник. Петя последовательно проводит в нём диагонали так, чтобы каждая вновь проведённая диагональ пересекала по внутренним точкам не более одной из проведённых ранее диагоналей. Какое наибольшее количество диагоналей может провести Петя?

На окружности отмечено 2<i>N</i> точек (<i>N</i> – натуральное число). Известно, что через любую точку внутри окружности проходит не более двух хорд с концами в отмеченных точках. Назовем <i>паросочетанием</i> такой набор из <i>N</i> хорд с концами в отмеченных точках, что каждая отмеченная точка является концом ровно одной из этих хорд. Назовём паросочетание <i>чётным</i>, если количество точек, в которых пересекаются его хорды, чётно, и <i>нечётным</i> иначе. Найдите разность между количеством чётных и нечётных паросочетаний.

  а) Три богатыря едут верхом по кольцевой дороге против часовой стрелки. Могут ли они ехать неограниченно долго с различными постоянными скоростями, если на дороге есть только одна точка, в которой богатыри имеют возможность обгонять друг друга?

  А если богатырей

  б) десять?

  в) тридцать три?

В стране 100 городов и несколько дорог. Каждая дорога соединяет два каких-то города, дороги не пересекаются. Из каждого города можно добраться до любого другого, двигаясь по дорогам. Докажите, что можно объявить несколько дорог главными так, чтобы из каждого города выходило нечётное число главных дорог.

Дана функция <i>f</i>(<i>x</i>), значение которой при любом целом <i>x</i> целое. Известно, что для любого простого числа <i>p</i> существует такой многочлен <i>Q_p</i>(<i>x</i>) степени, не превышающей 2013, с целыми коэффициентами, что  <i>f</i>(<i>n</i>) – <i>Q_p</i>(<i>n</i>)  делится на <i>p</i> при любом целом <i>n</i>. Верно ли, что существует такой многочлен <i>g</i>(<i>x</i>) с вещественными коэффициентами , что  <i>g</i>(<i>n</i>) = <i>f</i>(<i>n</i>)  для любого целого <i>n</i>?

<img align="right" src="/storage/problem-media/115364/problem_115364_img_2.gif"> Назовём лестницей высоты <i>n</i> фигуру, состоящую из всех клеток квадрата <i>n</i>×<i>n</i>, лежащих не выше диагонали (на рисунке показана лестница высоты 4). Сколькими различными способами можно разбить лестницу высоты <i>n</i> на несколько прямоугольников, стороны которых идут по линиям сетки, а площади попарно различны?

В каждой клетке квадрата 101<i>×</i>101, кроме центральной, стоит один из двух знаков: "поворот" или "прямо". Машинка въезжает извне в произвольную клетку на границе квадрата, после чего ездит параллельно сторонам клеток, придерживаясь двух правил:

  1) в клетке со знаком "прямо" она продолжает путь в том же направлении;

  2) в клетке со знаком "поворот" она поворачивает на 90° (в любую сторону по своему выбору).

Центральную клетку квадрата занимает дом. Можно ли расставить знаки так, чтобы у машинки не было возможности врезаться в дом?

В очереди к стоматологу стоят 30 ребят: мальчиков и девочек. Часы на стене показывают 8:00. Как только начинается новая минута, каждый мальчик, за которым стоит девочка, пропускает её вперед. Докажите, что перестановки в очереди закончатся до 8:30, когда откроется дверь кабинета.

В клетках таблицы 15×15 изначально записаны нули. За один ход разрешается выбрать любой её столбец или любую строку, стереть записанные там числа и записать туда все числа от 1 до 15 в произвольном порядке – по одному в каждую клетку. Какую максимальную сумму чисел в таблице можно получить такими ходами?

а) Докажите, что при<i> n></i>4любой выпуклый<i> n </i>-угольник можно разрезать на<i> n </i>тупоугольных треугольников.

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

в) На какое наименьшее число тупоугольных треугольников можно разрезать прямоугольник?

Даны положительные числа  <i>a</i>₁, <i>a</i>₂, ..., <i>a_n</i>.  Известно, что  <i>a</i>₁ + <i>a</i>₂ + ... + <i>a_n</i> ≤ ½.  Докажите, что  (1 + <i>a</i>₁)(1 + <i>a</i>₂)...(1 + <i>a_n</i>) < 2.

Последовательность<i> a</i>1<i>, a</i>2<i>,..,a</i>2000действительных чисел такова, что для любого натурального<i> n </i>,1<i><img src="/storage/problem-media/110026/problem_110026_img_2.gif"> n<img src="/storage/problem-media/110026/problem_110026_img_2.gif"></i>2000, выполняется равенство <center><i>

a</i>1<i></i>3<i>+a</i>2<i></i>3<i>+..+a_n</i>3<i>=</i>(<i>a</i>1<i>+a</i>2<i>+..+a_n</i>)<i></i>2<i>.

</i></center> Докажите, что все члены этой последовательности – целые числа.

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

Из бесконечной шахматной доски вырезали многоугольник со сторонами, идущими по сторонам клеток. Отрезок периметра многоугольника называется черным, если примыкающая к нему изнутри многоугольника клетка – черная, соответственно белым, если клетка белая. Пусть<i> A </i>– количество черных отрезков на периметре,<i> B </i>– количество белых, и пусть многоугольник состоит из<i> a </i>черных и<i> b </i>белых клеток. Докажите, что<i> A-B=</i>4(<i>a-b</i>).

Петя раскрашивает 2006 точек, расположенных на окружности, в 17 цветов. Затем Коля проводит хорды с концами в отмеченных точках так, чтобы концы любой хорды были одноцветны и хорды не имели общих точек (в том числе и общих концов). При этом Коля хочет провести как можно больше хорд, а Петя старается ему помешать. Какое наибольшее количество хорд заведомо сможет провести Коля?

В стране <i>n</i> городов. Между каждыми двумя из них проложена либо автомобильная, либо железная дорога. Турист хочет объехать страну, побывав в каждом городе ровно один раз, и вернуться в город, с которого он начинал путешествие. Докажите, что турист может выбрать город, с которого он начнет путешествие, и маршрут так, что ему придётся поменять вид транспорта не более одного раза.

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

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

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

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

Натуральные числа от 1 до 1000 по одному выписали на карточки, а затем накрыли этими карточками какие-то 1000 клеток прямоугольника1<i>x </i>1994. Если соседняя справа от карточки с числом<i> n </i>клетка свободна, то за один ход ее разрешается накрыть карточкой с числом<i> n+</i>1. Докажите, что нельзя сделать более полумиллиона таких ходов.

Докажите, что   <img align="absmiddle" src="/storage/problem-media/109540/problem_109540_img_2.gif">

Назовем усреднением последовательности<i>a_k </i>действительных чисел последовательность<i>a'_k </i>с общим членом<i> a'_k=<img src="/storage/problem-media/109520/problem_109520_img_2.gif"> </i>. Рассмотрим последовательности:<i>a_k </i>,<i>a'_k </i>– ее усреднение,<i>a''_k </i>– усреднение последовательности<i>a'_k </i>, и т.д. Если все эти последовательности состоят из целых чисел, то будем говорить, что последовательность<i>a_k </i>– хорошая. Докажите, что если последователь...

В строку записаны в некотором порядке натуральные числа от 1 до 1993. Над строкой производится следующая операция: если на первом месте стоит число <i>k</i>, то первые <i>k</i> чисел в строке переставляются в обратном порядке. Докажите, что через несколько таких операций на первом месте окажется число 1.

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