Олимпиадные задачи по теме «Индукция» - сложность 4 с решениями
Индукция
НазадВ каждую клетку квадратной таблицы размера (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>взвешиваний?
На табло горят несколько лампочек. Имеется несколько кнопок. Нажатие на кнопку меняет состояние лампочек, с которыми она соединена. Известно, что для любого набора лампочек найдется кнопка, соединенная с нечетным числом лампочек из этого набора. Докажите, что, нажимая на кнопки, можно погасить все лампочки.
Докажите, что для любого <i>k</i> > 1 найдётся такая степень двойки, что среди <i>k</i> последних её цифр не менее половины составляют девятки.
(Например, 2<sup>12</sup> = ...96, 2<sup>53</sup> = ...992.)
В коробке лежат карточки, занумерованные натуральными числами от <i>1</i> до <i>2006</i>. На карточке с номером <i>2006</i> лежит карточка с номером <i>2005</i> и т. д. до <i>1</i>. За ход разрешается взять одну верхнюю карточку (из любой коробки) и переложить ее либо на дно пустой коробки, либо на карточку с номером на единицу больше. Сколько пустых коробок нужно для того, чтобы переложить все карточки в другую коробку?
Докажите, что в пространстве существует такое расположение 2001 выпуклого многогранника, что никакие три из многогранников не имеют общих точек, а каждые два касаются друг друга (то есть имеют хотя бы одну граничную точку, но не имеют общих внутренних точек).
Система укреплений состоит из блиндажей. Некоторые из блиндажей соединены траншеями, причём из каждого блиндажа можно перебежать в какой-нибудь другой. В одном из блиндажей спрятался пехотинец. Пушка может одним выстрелом накрыть любой блиндаж. В каждом промежутке между выстрелами пехотинец обязательно перебегает по одной из траншей в соседний блиндаж (даже если по соседнему блиндажу только что стреляла пушка, пехотинец может туда перебежать). Назовём систему <i>надёжной</i>, если у пушки нет гарантированной стратегии поражения пехотинца (то есть такой последовательности выстрелов, благодаря которой пушка поразит пехотинца независимо от его начального местонахождения и последующих передвижений). <div align="center"><img src="/storage/problem-media/1050...
На лугу, имеющем форму квадрата, имеется круглая лунка. По лугу прыгает кузнечик. Перед каждым прыжком он выбирает вершину и прыгает по направлению к ней. Длина прыжка равна половине расстояния до этой вершины.
Сможет ли кузнечик попасть в лунку?
Для чисел 1, ..., 1999, расставленных по окружности, вычисляется сумма произведений всех наборов из 10 чисел, идущих подряд.
Найдите расстановку чисел, при которой полученная сумма наибольшая.
Кузнечик прыгает по отрезку [0,1]. За один прыжок он может попасть из точки x либо в точку x/3<sup>1/2</sup>, либо в точку x/3<sup>1/2</sup>+(1-(1/3<sup>1/2</sup>)). На отрезке [0,1] выбрана точка a.
Докажите, что, начиная из любой точки, кузнечик может через несколько прыжков оказаться на расстоянии меньше 1/100 от точки a.
В соревнованиях по <i>n</i>-борью участвуют 2<sup><i>n</i></sup> человек. Для каждого спортсмена известна его сила в каждом из видов программы. Соревнования проходят следующим образом: сначала все спортсмены участвуют в первом виде программы и лучшая половина из них выходит в следующий круг. Эта половина принимает участие в следующем виде и половина из них выходит в следующий круг, и т.д., пока в <i>n</i>-м виде программы не будет определен победитель. Назовем спортсмена <i>возможным победителем</i>, если можно так расставить виды спорта в программе, что он станет победителем.
а) Докажите, что может так случиться, что хотя бы половина спортсменов является возможными победителями.
б) Докажите, что число возможных по...
Имеется набор гирь, веса которых в граммах: 1, 2, 4,... , 512 (последовательные степени двойки) – по одной гире каждого веса. Груз разрешается взвешивать с помощью этого набора, кладя гири на обе чашки весов.
а) Докажите, что никакой груз нельзя взвесить этими гирями более чем 89 способами.
б) Приведите пример груза, который можно взвесить ровно 89 способами.
В соревновании участвуют 16 боксёров. Каждый боксёр в течение одного дня может проводить только один бой. Известно, что все боксёры имеют разную силу, и что сильнейший всегда выигрывает. Докажите, что за 10 дней можно определить место каждого боксёра.
(Расписание каждого дня соревнований составляется вечером накануне и в день соревнований не изменяется.)
Каждая клетка шахматной доски закрашена в один из цветов – синий или красный. Докажите, что клетки одного из цветов обладают тем свойством, что их может обойти шахматный ферзь (на клетках этого цвета ферзь может побывать не один раз, на клетки другого цвета он не ставится, но может через них перепрыгивать).
а) Доказать, что для любых положительных чисел <i>x</i><sub>1</sub>, <i>x</i><sub>2</sub>, ..., <i>x<sub>k</sub></i> (<i>k</i> > 3) выполняется неравенство: <div align="center"><img src="/storage/problem-media/97781/problem_97781_img_2.gif"></div>б) Доказать, что это неравенство ни для какого <i>k</i> > 3 нельзя усилить, то есть доказать, что для каждого фиксированного <i>k</i> нельзя заменить двойку в правой части на большее число так, чтобы полученное неравенство было справедливо для любого набора из <i>k</i> положительных чисел.
На прямоугольном листе бумаги нарисован круг, внутри которого Миша мысленно выбирает<i>n</i>точек, а Коля пытается их разгадать. За одну попытку Коля указывает на листе (внутри или вне круга) одну точку, а Миша сообщает Коле расстояние от нее до ближайшей неразгаданной точки. Если оно оказывается нулевым, то после этого указанная точка считается разгаданной. Коля умеет отмечать на листе точки, откладывать расстояния и производить построения циркулем и линейкой. Может ли Коля наверняка разгадать все выбранные точки менее, чем за (<i>n</i>+1)<sup>2</sup>попыток?
В пространстве даны 200 точек. Каждые две из них соединены отрезком, причём отрезки не пересекаются друг с другом. Первый игрок красит каждый отрезок в один из <i>k</i> цветов, затем второй игрок красит в один из тех же цветов каждую точку. Если найдутся две точки и отрезок между ними, окрашенные в один цвет, выигрывает первый игрок, в противном случае второй. Докажите, что первый может гарантировать себе выигрыш, если
а) <i>k</i> = 7; б) <i>k</i> = 10.
Можно ли выбрать некоторые натуральные числа так, чтобы при любом натуральном значении<i>n</i>хотя бы одно из чисел<i>n</i>,<i>n</i>+ 50 было выбрано и хотя бы одно из чисел<i>n</i>,<i>n</i>+ 1987 не было выбрано?
В пространстве расположены 2<i>n</i> точек, никакие четыре из которых не лежат в одной плоскости. Проведены <i>n</i>² + 1 отрезков с концами в этих точках. Докажите, что проведённые отрезки образуют
а) хотя бы один треугольник;
б) не менее <i>n</i> треугольников.
На химической конференции присутствовало<i>k</i>учёных химиков и алхимиков, причём химиков было больше, чем алхимиков. Известно, что на любой вопрос химики всегда отвечают правду, а алхимики иногда говорят правду, а иногда лгут. Оказавшийся на конференции математик про каждого учёного хочет установить, химик тот или алхимик. Для этого он любому учёному может задать вопрос: "Кем является такой-то: химиком или алхимиком?" (В частности, может спросить, кем является сам этот учёный.) Доказать, что математик может установить это за 2<i>k</i>− 3 вопросов.