Олимпиадные задачи по теме «Индукция» для 8-9 класса - сложность 4-5 с решениями
Индукция
НазадВ королевстве <i>N</i> городов, некоторые пары которых соединены непересекающимися дорогами с двусторонним движением (города из такой пары называются <i>соседними</i>). При этом известно, что из каждого города можно доехать до любого другого, но невозможно, выехав из некоторого города и двигаясь по различным дорогам, вернуться в исходный город.
Однажды Король провел такую реформу: каждый из <i>N</i> мэров городов стал снова мэром одного из <i>N</i> городов, но, возможно, не того города, в котором он работал до реформы. Оказалось, что каждые два мэра, работавшие в соседних городах до реформы, оказались в соседних городах и после реформы. Докажите, что либо найдётся город, в котором мэр после реформы не поменялся, либо найдётся пара сос...
В нашем распоряжении имеются 3<sup>2<i>k</i></sup>неотличимых по виду монет, одна из которых фальшивая– она весит чуть легче настоящей. Кроме того, у нас есть трое двухчашечных весов. Известно, что двое весов исправны, а одни– сломаны (показываемый ими исход взвешивания никак не связан с весом положенных на них монет, т.е. может быть как верным, так и искаженным в любую сторону, причем на разных взвешиваниях– искаженным по-разному). При этом неизвестно, какие именно весы исправны, а какие сломаны. Как определить фальшивую монету за 3<i>k + </i>1 взвешиваний?
Последовательности(<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 карточек на стол слева направо так, чтобы числа на них располагались в порядке возрастания?
За круглым столом сидят 100 представителей 25 стран, по 4 представителя от каждой. Докажите, что их можно разбить на 4 группы таким образом, что в каждой группе будет по одному представителю от каждой страны, и никакие двое из одной группы не сидят за столом рядом.
У Ани и Бори было по длинной полосе бумаги. На одной из них была написана буква А, на другой – Б. Каждую минуту один из них (не обязательно по очереди) приписывает справа или слева к слову на своей полосе слово с полосы другого. Докажите, что через сутки слово с Аниной полосы можно будет разрезать на 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>, если каждое число равно произведению всех соседних с ним (соседними считаются числа, стоящие в клетках с общей стороной). Найдите число удачных расстановок.
На бесконечной в обе стороны полосе из клеток, пронумерованных целыми числами, лежит несколько камней (возможно, по нескольку в одной клетке). Разрешается выполнять следующие действия:<ol> <li> Снять по одному камню с клеток <i> n-</i>1 и <i> n </i> и положить один камень в клетку <i> n+</i>1; </li> <li> Снять два камня с клетки <i> n </i> и положить по одному камню в клетки <i> n+</i>1, <i> n-</i>2.</li></ol>Докажите, что при любой последовательности действий мы достигнем ситуации, когда указанные действия больше выполнять нельзя, и эта конечная ситуация не зависит от последовательности действий (а зависит только от начальной раскладки камней по клеткам).
В прямоугольную коробку с основанием <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>различных красных точек. Докажите, что сумма попарных расстояний между точками одного цвета не превосходит суммы попарных расстояний между точками разного цвета.