Олимпиадные задачи по теме «Индукция» - сложность 3 с решениями
Индукция
НазадКуб с ребром2<i>n+</i>1разрезают на кубики с ребром 1 и бруски размера2<i>x </i>2<i>x </i>1. Какое наименьшее количество единичных кубиков может при этом получиться?
Набор чисел<i>a</i><sub>0</sub>,<i>a</i><sub>1</sub>, ...,<i>a<sub>n</sub></i>удовлетворяет условиям: <i>a</i><sub>0</sub>= 0, 0 ≤<i>a</i><sub><i>k</i>+1</sub>–<i>a<sub>k</sub></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><sub>0</sub>, <i>a</i><sub>1</sub>, ..., <i>a<sub>n</sub></i> удовлетворяет условиям: <i>a</i><sub>0</sub> = 0, <i>a</i><sub><i>k</i>+1</sub> ≥ <i>a</i><sub><i>k</i></sub> + 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 клеток можно разбить на пары клеток, лежащих в одной строке или в одном столбце.
Последовательность<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<sub>n</sub></i>3<i>=</i>(<i>a</i>1<i>+a</i>2<i>+..+a<sub>n</sub></i>)<i></i>2<i>.
</i></center> Докажите, что все члены этой последовательности – целые числа.
В классе каждый болтун дружит хотя бы с одним молчуном. При этом болтун молчит, если в кабинете находится нечетное число его друзей – молчунов. Докажите, что учитель может пригласить на факультатив не менее половины класса так, чтобы все болтуны молчали.
Из бесконечной шахматной доски вырезали многоугольник со сторонами, идущими по сторонам клеток. Отрезок периметра многоугольника называется черным, если примыкающая к нему изнутри многоугольника клетка – черная, соответственно белым, если клетка белая. Пусть<i> A </i>– количество черных отрезков на периметре,<i> B </i>– количество белых, и пусть многоугольник состоит из<i> a </i>черных и<i> b </i>белых клеток. Докажите, что<i> A-B=</i>4(<i>a-b</i>).
Числовая последовательность<i> a<sub>0</sub> </i>,<i> a<sub>1</sub> </i>,<i> a<sub>2</sub> </i>, такова, что при всех неотрицательных<i> m </i>и<i> n </i>(<i> m<img src="/storage/problem-media/109861/problem_109861_img_2.gif"> n </i>) выполняется соотношение <center><i>
a<sub>m+n</sub>+a<sub>m-n</sub>=<img src="/storage/problem-media/109861/problem_109861_img_3.gif"></i>(<i>a</i>2<i>m+a</i>2<i>n</i>)<i>.
</i></center> Найдите<i> a</i>1995, если<i> a<sub>1</sub>=</i>1.
Петя раскрашивает 2006 точек, расположенных на окружности, в 17 цветов. Затем Коля проводит хорды с концами в отмеченных точках так, чтобы концы любой хорды были одноцветны и хорды не имели общих точек (в том числе и общих концов). При этом Коля хочет провести как можно больше хорд, а Петя старается ему помешать. Какое наибольшее количество хорд заведомо сможет провести Коля?
Последовательности положительных чисел (<i>x<sub>n</sub></i>) и (<i>y<sub>n</sub></i>) удовлетворяют условиям <img align="absmiddle" src="/storage/problem-media/109842/problem_109842_img_2.gif"> при всех натуральных <i>n</i>. Докажите, что если все числа <i>x</i><sub>1</sub>, <i>x</i><sub>2</sub>, <i>y</i><sub>1</sub>, <i>y</i><sub>2</sub> больше 1, то <i>x<sub>n</sub> > y<sub>n</sub></i> при каком-нибудь натуральном <i>n</i>.
В стране <i>n</i> городов. Между каждыми двумя из них проложена либо автомобильная, либо железная дорога. Турист хочет объехать страну, побывав в каждом городе ровно один раз, и вернуться в город, с которого он начинал путешествие. Докажите, что турист может выбрать город, с которого он начнет путешествие, и маршрут так, что ему придётся поменять вид транспорта не более одного раза.
В компании из 2<i>n</i> + 1 человека для любых <i>n</i> человек найдётся отличный от них человек, знакомый с каждым из них.
Докажите, что в этой компании есть человек, знающий всех.
Внутри параболы <i>y = x</i>² расположены несовпадающие окружности ω<sub>1</sub>, ω<sub>2</sub>, ω<sub>3</sub>, ... так, что при каждом <i>n</i> > 1 окружность ω<sub><i>n</i></sub> касается ветвей параболы и внешним образом окружности ω<sub><i>n</i>–1</sub> (см. рис.). Найдите радиус окружности σ<sub>1998</sub>, если известно, что диаметр ω<sub>1</sub> равен 1 и она касается параболы в её вершине. <div align="center"><img src="/storage/problem-media/109664/problem_109664_img_2.gif"></div>
В один из дней года оказалось, что каждый житель города сделал не более одного звонка по телефону. Докажите, что население города можно разбить не более чем на три группы так, чтобы жители, входящие в одну группу, не разговаривали в этот день между собой по телефону.
Плоскость разбита двумя семействами параллельных прямых на единичные квадратики. Назовем каемкой квадрата<i>n</i>×<i>n</i>, состоящего из квадратиков разбиения, объединение тех квадратиков, которые хотя бы одной из своих сторон примыкают изнутри к его границе. Докажите, что существует ровно один способ покрытия квадрата100<i>×</i>100, состоящего из квадратиков разбиения, неперекрывающимися каемками пятидесяти квадратов. (Каемки могут и не содержаться в квадрате100<i>× </i>100.)
Натуральные числа от 1 до 1000 по одному выписали на карточки, а затем накрыли этими карточками какие-то 1000 клеток прямоугольника1<i>x </i>1994. Если соседняя справа от карточки с числом<i> n </i>клетка свободна, то за один ход ее разрешается накрыть карточкой с числом<i> n+</i>1. Докажите, что нельзя сделать более полумиллиона таких ходов.
Докажите, что <img align="absmiddle" src="/storage/problem-media/109540/problem_109540_img_2.gif">
Назовем усреднением последовательности<i>a<sub>k</sub> </i>действительных чисел последовательность<i>a'<sub>k</sub> </i>с общим членом<i> a'<sub>k</sub>=<img src="/storage/problem-media/109520/problem_109520_img_2.gif"> </i>. Рассмотрим последовательности:<i>a<sub>k</sub> </i>,<i>a'<sub>k</sub> </i>– ее усреднение,<i>a''<sub>k</sub> </i>– усреднение последовательности<i>a'<sub>k</sub> </i>, и т.д. Если все эти последовательности состоят из целых чисел, то будем говорить, что последовательность<i>a<sub>k</sub> </i>– хорошая. Докажите, что если последователь...
В строку записаны в некотором порядке натуральные числа от 1 до 1993. Над строкой производится следующая операция: если на первом месте стоит число <i>k</i>, то первые <i>k</i> чисел в строке переставляются в обратном порядке. Докажите, что через несколько таких операций на первом месте окажется число 1.
С ненулевым числом разрешается проделывать следующие операции:<i> x<img src="/storage/problem-media/109493/problem_109493_img_2.gif"> <img src="/storage/problem-media/109493/problem_109493_img_3.gif"> </i>,<i> x<img src="/storage/problem-media/109493/problem_109493_img_2.gif"> <img src="/storage/problem-media/109493/problem_109493_img_4.gif"> </i>. Верно ли, что из каждого ненулевого рационального числа можно получить каждое рациональное число с помощью конечного числа таких операций?
Среди 300 учеников одной математической школы некоторые путают лево и право, некоторые не путают, а некоторые делают все наоборот, чем им говорят. Первого сентября всех учеников выстроили в одну шеренгу (плечом к плечу) и скомандовали "нале-во!" По этой команде все одновременно повернулись на 90°, кто налево, а кто направо. Ровно через секунду каждый, кто оказался лицом к лицу к соседу, понимает, что не прав, и поворачивается кругом (на 180°). Как долго это может продолжаться?
Единичный квадрат разбит на конечное число квадратиков (размеры которых могут различаться). Может ли сумма периметров квадратиков, пересекающихся с главной диагональю, быть больше 1993? (Если квадратик пересекается с диагональю по одной точке, это тоже считается пересечением.)
Дед барона К.Ф.И. фон Мюнхгаузена построил квадратный замок, разделил его на 9 квадратных залов и в центральном разместил арсенал. Отец барона разделил каждый из восьми оставшихся залов на 9 равных квадратных холлов и во всех центральных холлах устроил зимние сады. Сам барон разделил каждый из 64 свободных холлов на 9 равных квадратных комнат и в каждой из центральных комнат устроил бассейн, а остальные сделал жилыми. Барон хвастается, что ему удалось обойти все жилые комнаты, побывав в каждой по одному разу, и вернуться в исходную (в каждой стене между двумя соседними жилыми комнатами проделана дверь). Могут ли слова барона быть правдой?
Найдите <i>x</i><sub>1000</sub>, если <i>x</i><sub>1</sub> = 4, <i>x</i><sub>2</sub> = 6, и при любом натуральном <i>n</i> ≥ 3 <i>x<sub>n</sub></i> – наименьшее составное число, большее 2<i>x</i><sub><i>n</i>–1</sub> – <i>x</i><sub><i>n</i>–2</sub>.
Существует ли конечное слово из букв русского алфавита, в котором нет двух соседних одинаковых подслов, но таковые появляются при приписывании (как справа, так и слева) любой буквы русского алфавита.Комментарий.<i>Словом</i>мы называем любую последовательность букв русского алфавита, не обязательно осмысленную,<i>подсловом</i>называется любой фрагмент слова. Например, АБВШГАБ - слово, а АБВ, Ш, ШГАБ - его подслова.