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

Существуют ли 2013 таких различных натуральных чисел, что сумма каждых двух из них делится на их разность?

Даны  <i>n</i> + 1  попарно различных натуральных чисел, меньших 2<i>n</i>  (<i>n</i> > 1).

Докажите, что среди них найдутся три таких числа, что сумма двух из них равна третьему.

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

55 боксёров участвовали в турнире по системе "проигравший выбывает". Бои шли последовательно. Известно, что у участников каждого боя число предыдущих побед отличалось не более чем на 1. Какое наибольшее число боёв мог провести победитель турнира?

Дана функция <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>?

  В королевстве <i>N</i> городов, некоторые пары которых соединены непересекающимися дорогами с двусторонним движением (города из такой пары называются <i>соседними</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° (в любую сторону по своему выбору).

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

В нашем распоряжении имеются 3^2<i>k</i>неотличимых по виду монет, одна из которых фальшивая– она весит чуть легче настоящей. Кроме того, у нас есть трое двухчашечных весов. Известно, что двое весов исправны, а одни– сломаны (показываемый ими исход взвешивания никак не связан с весом положенных на них монет, т.е. может быть как верным, так и искаженным в любую сторону, причем на разных взвешиваниях– искаженным по-разному). При этом неизвестно, какие именно весы исправны, а какие сломаны. Как определить фальшивую монету за 3<i>k + </i>1 взвешиваний?

Последовательности(<i>a_n</i>)и(<i>b_n</i>)заданы условиями<i> a₁=</i>1,<i> b₁=</i>2,<i> a_n+</i>1<i>=<img src="/storage/problem-media/111872/problem_111872_img_2.gif"> </i>и<i> b_n+</i>1<i>=<img src="/storage/problem-media/111872/problem_111872_img_3.gif"> </i>. Докажите, что<i> a</i>2008<i><</i>5.

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

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

Для положительных чисел <i>x</i>₁, <i>x</i>₂, ..., <i>x_n</i> докажите неравенство   <img align="absmiddle" src="/storage/problem-media/111769/problem_111769_img_2.gif">

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

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

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

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

Тест состоит из 30 вопросов, на каждый есть два варианта ответа (один верный, другой нет). За одну попытку Витя отвечает на все вопросы, после чего ему сообщают, на сколько вопросов он ответил верно. Сможет ли Витя действовать так, чтобы гарантированно узнать все верные ответы не позже, чем

  а) после 29-й попытки (и ответить верно на все вопросы при 30-й попытке);

  б) после 24-й попытки (и ответить верно на все вопросы при 25-й попытке)? (Изначально Витя не знает ни одного ответа, тест всегда один и тот же.)

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

  а) число 1 встреч...

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

  а) Докажите, что полусумма чисел одной чётности одного цвета всегда окрашена в тот же цвет.

  б) При каких <i>N</i> такая раскраска возможна?

Диагональ правильного 2006-угольника <i>P</i> называется <i>хорошей</i>, если её концы делят границу <i>P</i> на две части, каждая из которых содержит нечётное число сторон. Стороны <i>P</i> также называются хорошими. Пусть <i>P</i> разбивается на треугольники 2003 диагоналями, никакие две из которых не имеют общих точек внутри <i>P</i>. Какое наибольшее число равнобедренных треугольников, каждый из которых имеет две хорошие стороны, может иметь такое разбиение?