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

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

  Однажды Король провел такую реформу: каждый из <i>N</i> мэров городов стал снова мэром одного из <i>N</i> городов, но, возможно, не того города, в котором он работал до реформы. Оказалось, что каждые два мэра, работавшие в соседних городах до реформы, оказались в соседних городах и после реформы. Докажите, что либо найдётся город, в котором мэр после реформы не поменялся, либо найдётся пара сос...

Последовательность<i> a₁,a₂,.. </i>такова, что<i> a₁<img align="absmiddle" src="/storage/problem-media/115397/problem_115397_img_2.gif"></i>(1<i>,</i>2)и<i> a_k+</i>1<i>=a_k+<img align="absmiddle" src="/storage/problem-media/115397/problem_115397_img_3.gif"> </i>при любом натуральном <i> k </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>. Какое наибольшее число равнобедренных треугольников, каждый из которых имеет две хорошие стороны, может иметь такое разбиение?

Куб с ребром2<i>n+</i>1разрезают на кубики с ребром 1 и бруски размера2<i>x </i>2<i>x </i>1. Какое наименьшее количество единичных кубиков может при этом получиться?

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

Докажите, что если натуральное число <i>N</i> представляется в виде суммы трёх квадратов целых чисел, делящихся на 3, то оно также представляется в виде суммы трёх квадратов целых чисел, не делящихся на 3.

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

Набор чисел<i>a</i>₀,<i>a</i>₁, ...,<i>a_n</i>удовлетворяет условиям:  <i>a</i>₀= 0,  0 ≤<i>a</i>_<i>k</i>+1–<i>a_k</i>≤ 1  при  <i>k</i>= 0, 1, ...,<i>n</i>– 1.  Докажите неравенство  <img align="absmiddle" src="/storage/problem-media/110096/problem_110096_img_2.gif">

Набор чисел <i>a</i>₀, <i>a</i>₁, ..., <i>a_n</i> удовлетворяет условиям:  <i>a</i>₀ = 0,  <i>a</i>_<i>k</i>+1 ≥ <i>a</i>_<i>k</i> + 1  при  <i>k</i> = 0, 1, ..., <i>n</i> – 1.  Докажите неравенство   <img align="absmiddle" src="/storage/problem-media/110087/problem_110087_img_2.gif">

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

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