Олимпиадные задачи по теме «Индукция» для 9 класса - сложность 4 с решениями
Индукция
НазадВ королевстве <i>N</i> городов, некоторые пары которых соединены непересекающимися дорогами с двусторонним движением (города из такой пары называются <i>соседними</i>). При этом известно, что из каждого города можно доехать до любого другого, но невозможно, выехав из некоторого города и двигаясь по различным дорогам, вернуться в исходный город.
Однажды Король провел такую реформу: каждый из <i>N</i> мэров городов стал снова мэром одного из <i>N</i> городов, но, возможно, не того города, в котором он работал до реформы. Оказалось, что каждые два мэра, работавшие в соседних городах до реформы, оказались в соседних городах и после реформы. Докажите, что либо найдётся город, в котором мэр после реформы не поменялся, либо найдётся пара сос...
Последовательности(<i>a<sub>n</sub></i>)и(<i>b<sub>n</sub></i>)заданы условиями<i> a<sub>1</sub>=</i>1,<i> b<sub>1</sub>=</i>2,<i> a<sub>n+</sub></i>1<i>=<img src="/storage/problem-media/111872/problem_111872_img_2.gif"> </i>и<i> b<sub>n+</sub></i>1<i>=<img src="/storage/problem-media/111872/problem_111872_img_3.gif"> </i>. Докажите, что<i> a</i>2008<i><</i>5.
Для положительных чисел <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>N</i> представляется в виде суммы трёх квадратов целых чисел, делящихся на 3, то оно также представляется в виде суммы трёх квадратов целых чисел, не делящихся на 3.
В стране 2000 городов, некоторые пары городов соединены дорогами. Известно, что через любой город проходит не более <i>N</i> различных несамопересекающихся циклических маршрутов нечётной длины. Докажите, что страну можно разделить на <i>N</i> + 2 республики так, чтобы никакие два города из одной республики не были соединены дорогой.
За круглым столом сидят 100 представителей 50 стран, по двое от каждой страны. Докажите, что их можно разбить на две группы таким образом, что в каждой группе будет по одному представителю от каждой страны, и каждый человек находился в одной группе не более чем с одним своим соседом.
На столе лежат 365 карточек, на обратной стороне которых написаны различные числа. За один рубль Вася может выбрать три карточки и попросить Петю положить их слева направо так, чтобы числа на карточках располагались в порядке возрастания. Может ли Вася, потратив 2000 рублей, с гарантией выложить все 365 карточек на стол слева направо так, чтобы числа на них располагались в порядке возрастания?
У Ани и Бори было по длинной полосе бумаги. На одной из них была написана буква А, на другой – Б. Каждую минуту один из них (не обязательно по очереди) приписывает справа или слева к слову на своей полосе слово с полосы другого. Докажите, что через сутки слово с Аниной полосы можно будет разрезать на 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> 1,1,2,3,5,8,13,21,34,..., </i>каждое из которых, начиная с третьего, равно сумме двух предыдущих. Доказать, что каждое натуральное число<i> n>2 </i>равно сумме нескольких различных чисел указанного ряда.
В ящиках лежат камни. За один ход выбирается число <i>k</i>, затем камни в ящиках делятся на группы по <i>k</i> штук и остаток менее, чем из <i>k</i> штук. Оставляют по одному камню из каждой группы и весь остаток. Можно ли за пять ходов добиться, чтобы в ящиках осталось ровно по одному камню, если в каждом из них
а) не более 460 камней;
б) не более 461 камня?
Банкир узнал, что среди одинаковых на вид монет одна — фальшивая (более легкая). Он попросил эксперта определить эту монету с помощью чашечных весов без гирь, причем потребовал, чтобы каждая монета участвовала во взвешиваниях не более двух раз. Какое наибольшее число монет может быть у банкира, чтобы эксперт заведомо смог выделить фальшивую за<i>n</i>взвешиваний?
На табло горят несколько лампочек. Имеется несколько кнопок. Нажатие на кнопку меняет состояние лампочек, с которыми она соединена. Известно, что для любого набора лампочек найдется кнопка, соединенная с нечетным числом лампочек из этого набора. Докажите, что, нажимая на кнопки, можно погасить все лампочки.