Олимпиадные задачи по теме «Индукция» для 11 класса - сложность 4 с решениями
Индукция
НазадНа координатной плоскости нарисовано <i>n</i> парабол, являющихся графиками квадратных трёхчленов; никакие две из них не касаются. Они делят плоскость на несколько областей, одна из которых расположена над всеми параболами. Докажите, что у границы этой области не более 2(<i>n</i> – 1) углов (то есть точек пересечения пары парабол).
Изначально на доске были написаны одночленs 1, <i>x, x</i>², ..., <i>x<sup>n</sup></i>. Договорившись заранее, <i>k</i> мальчиков каждую минуту одновременно вычисляли каждый сумму каких-то двух многочленов, написанных на доске, и результат дописывали на доску. Через <i>m</i> минут на доске были написаны, среди прочих, многочлены <i>S</i><sub>1</sub> = 1 + <i>x, S</i><sub>2</sub> = 1 + <i>x + x</i>², <i>S</i><sub>3</sub> = 1 + <i>x + x</i>² + <i>x</i><sup>3</sup>, ..., <i>S<sub>n</sub></i> = 1 + <i>x + x</i>² + ... + <i>x<sup>n</sup></i>. Докажите...
У Кости была кучка из 100 камешков. Каждым ходом он делил какую-то из кучек на две меньших, пока у него в итоге не оказалось
100 кучек по одному камешку. Докажите, что
а) в какой-то момент в каких-то 30 кучках было в сумме ровно 60 камешков;
б) в какой-то момент в каких-то 20 кучках было в сумме ровно 60 камешков;
в) Костя мог действовать так, чтобы ни в какой момент не нашлось 19 кучек, в которых в сумме ровно 60 камешков.
Квадрат <i>ABCD</i> разрезан на одинаковые прямоугольники с целыми длинами сторон. Фигура <i>F</i> является объединением всех прямоугольников, имеющих общие точки с диагональю <i>AC</i>. Докажите, что <i>AC</i> делит площадь фигуры <i>F</i> пополам.
В каждой клетке таблицы 1000×1000 стоит ноль или единица. Докажите, что можно либо вычеркнуть 990 строк так, что каждом столбце будет хотя бы одна невычеркнутая единица, либо вычеркнуть 990 столбцов так, что в каждой строке будет хотя бы один невычеркнутый ноль.
В королевстве <i>N</i> городов, некоторые пары которых соединены непересекающимися дорогами с двусторонним движением (города из такой пары называются <i>соседними</i>). При этом известно, что из каждого города можно доехать до любого другого, но невозможно, выехав из некоторого города и двигаясь по различным дорогам, вернуться в исходный город.
Однажды Король провел такую реформу: каждый из <i>N</i> мэров городов стал снова мэром одного из <i>N</i> городов, но, возможно, не того города, в котором он работал до реформы. Оказалось, что каждые два мэра, работавшие в соседних городах до реформы, оказались в соседних городах и после реформы. Докажите, что либо найдётся город, в котором мэр после реформы не поменялся, либо найдётся пара сос...
Последовательность<i> a<sub>1</sub>,a<sub>2</sub>,.. </i>такова, что<i> a<sub>1</sub><img align="absmiddle" src="/storage/problem-media/115397/problem_115397_img_2.gif"></i>(1<i>,</i>2)и<i> a<sub>k+</sub></i>1<i>=a<sub>k</sub>+<img align="absmiddle" src="/storage/problem-media/115397/problem_115397_img_3.gif"> </i>при любом натуральном <i> k </i>. Докажите, что в ней не может существовать более одной пары членов с целой суммой.
Для положительных чисел <i>x</i><sub>1</sub>, <i>x</i><sub>2</sub>, ..., <i>x<sub>n</sub></i> докажите неравенство <img align="absmiddle" src="/storage/problem-media/111769/problem_111769_img_2.gif">
На столе лежат купюры достоинством 1, 2,<i> .. </i>,2<i>n </i>тугриков. Двое ходят по очереди. Каждым ходом игрок снимает со стола две купюры, большую отдает сопернику, а меньшую забирает себе. Каждый стремится получить как можно больше денег. Сколько тугриков получит начинающий при правильной игре?
Тест состоит из 30 вопросов, на каждый есть два варианта ответа (один верный, другой нет). За одну попытку Витя отвечает на все вопросы, после чего ему сообщают, на сколько вопросов он ответил верно. Сможет ли Витя действовать так, чтобы гарантированно узнать все верные ответы не позже, чем
а) после 29-й попытки (и ответить верно на все вопросы при 30-й попытке);
б) после 24-й попытки (и ответить верно на все вопросы при 25-й попытке)? (Изначально Витя не знает ни одного ответа, тест всегда один и тот же.)
В бесконечной последовательности <i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>, <i>a</i><sub>3</sub>, ... число <i>a</i><sub>1</sub> равно 1, а каждое следующее число <i>a<sub>n</sub></i> строится из предыдущего <i>a</i><sub><i>n</i>–1</sub> по правилу: если у числа <i>n</i> наибольший нечётный делитель имеет остаток 1 от деления на 4, то <i>a<sub>n</sub> = a</i><sub><i>n</i>–1</sub> + 1, если же остаток равен 3, то <i>a<sub>n</sub> = a</i><sub><i>n</i>–1</sub> – 1. Докажите, что в этой последовательности
а) число 1 встреч...
Натуральные числа покрашены в <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>. Какое наибольшее число равнобедренных треугольников, каждый из которых имеет две хорошие стороны, может иметь такое разбиение?
Каждой стороне<i>b</i>выпуклого многоугольника<i>P</i>поставлена в соответствие наибольшая из площадей треугольников, содержащихся в<i>P</i>, одна из сторон которых совпадает с<i>b</i>. Докажите, что сумма площадей, соответствующих всем сторонам<i>P</i>, не меньше удвоенной площади многоугольника<i>P</i>.
На плоскости рассматривается конечное множество равных, параллельно расположенных квадратов, причем среди любых<i> k+</i>1квадратов найдутся два пересекающихся. Докажите, что это множество можно разбить не более чем на2<i>k-</i>1непустых подмножеств так, что в каждом подмножестве все квадраты будут иметь общую точку.
У Ани и Бори было по длинной полосе бумаги. На одной из них была написана буква А, на другой – Б. Каждую минуту один из них (не обязательно по очереди) приписывает справа или слева к слову на своей полосе слово с полосы другого. Докажите, что через сутки слово с Аниной полосы можно будет разрезать на 2 части и переставить их местами так, что получится то же слово, записанное в обратном порядке.
Докажите, что существует бесконечно много натуральных <i>n</i>, для которых числитель несократимой дроби, равной 1 + ½ + ... + <sup>1</sup>/<sub><i>n</i></sub>, не является степенью простого числа с натуральным показателем.
В городе несколько площадей. Некоторые пары площадей соединены улицами с односторонним движением так, что с каждой площади можно выехать ровно по двум улицам. Докажите, что город можно разделить на 1014 районов так, чтобы улицами соединялись только площади из разных районов, и для каждых двух районов все соединяющие их улицы были направлены одинаково (либо все из первого района во второй, либо наоборот).
На прямоугольном столе лежат равные картонные квадраты<i> n </i>различных цветов со сторонами, параллельными сторонам стола. Если рассмотреть любые<i> n </i>квадратов различных цветов, то какие-нибудь два из них можно прибить к столу одним гвоздем. Докажите, что все квадраты некоторого цвета можно прибить к столу2<i>n-</i>2гвоздями.
Дана последовательность неотрицательных чисел<i> a<sub>1</sub> </i>,<i> a<sub>2</sub> </i>,<i> a<sub>n</sub> </i>. Для любого<i> k </i>от 1 до<i> n </i>обозначим через<i> m<sub>k</sub> </i>величину <center><i>
<img src="/storage/problem-media/109710/problem_109710_img_2.gif"><sub>l=</sub></i>1<i>,</i>2<i>,..,k <img src="/storage/problem-media/109710/problem_109710_img_3.gif">.
</i></center> Докажите, что при любом<i> α></i>0число тех<i> k </i>, для которых<i> m<sub>k</sub>>α </i>, меньше, чем<i>a<sub>1</sub>+...
В каждую клетку квадратной таблицы размера (2<sup><i>n</i></sup> – 1)×(2<sup><i>n</i></sup> – 1) ставится одно из чисел 1 или – 1. Расстановку чисел назовём <i>удачной</i>, если каждое число равно произведению всех соседних с ним (соседними считаются числа, стоящие в клетках с общей стороной). Найдите число удачных расстановок.
В прямоугольную коробку с основанием <i>m</i>×<i>n</i>, где <i>m</i> и <i>n</i> – нечётные числа, уложены домино размера 2×1 так, что остался не покрыт только квадрат 1×1 (дырка) в углу коробки. Если доминошка прилегает к дырке короткой стороной, её разрешается сдвинуть вдоль себя на одну клетку, закрыв дырку (при этом открывается новая дырка). Докажите, что с помощью таких передвижений можно перегнать дырку в любой другой угол.
Внутри круга расположены точки <i>A</i><sub>1</sub>, <i>A</i><sub>2</sub>, ..., <i>A<sub>n</sub></i>, а на его границе – точки <i>B</i><sub>1</sub>, <i>B</i><sub>2</sub>, ..., <i>B<sub>n</sub></i> так, что отрезки <i>A</i><sub>1</sub><i>B</i><sub>1</sub>, <i>A</i><sub>2</sub><i>B</i><sub>2</sub>, ..., <i>A<sub>n</sub>B<sub>n</sub></i> не пересекаются. Кузнечик может перепрыгнуть из точки <i>A<sub>i</sub></i> в точку <i>A<sub>j</sub></i>, если отрезок <i>A<sub>...
На прямой отмечены<i> n </i>различных синих точек и<i> n </i>различных красных точек. Докажите, что сумма попарных расстояний между точками одного цвета не превосходит суммы попарных расстояний между точками разного цвета.
В ящиках лежат камни. За один ход выбирается число <i>k</i>, затем камни в ящиках делятся на группы по <i>k</i> штук и остаток менее, чем из <i>k</i> штук. Оставляют по одному камню из каждой группы и весь остаток. Можно ли за пять ходов добиться, чтобы в ящиках осталось ровно по одному камню, если в каждом из них
а) не более 460 камней;
б) не более 461 камня?