Олимпиадные задачи по теме «Индукция» для 10 класса - сложность 5 с решениями

В нашем распоряжении имеются 3^2<i>k</i>неотличимых по виду монет, одна из которых фальшивая– она весит чуть легче настоящей. Кроме того, у нас есть трое двухчашечных весов. Известно, что двое весов исправны, а одни– сломаны (показываемый ими исход взвешивания никак не связан с весом положенных на них монет, т.е. может быть как верным, так и искаженным в любую сторону, причем на разных взвешиваниях– искаженным по-разному). При этом неизвестно, какие именно весы исправны, а какие сломаны. Как определить фальшивую монету за 3<i>k + </i>1 взвешиваний?

Докажите, что выпуклый многоугольник может быть разрезан непересекающимися диагоналями на остроугольные треугольники не более, чем одним способом.

За круглым столом сидят 100 представителей 25 стран, по 4 представителя от каждой. Докажите, что их можно разбить на 4 группы таким образом, что в каждой группе будет по одному представителю от каждой страны, и никакие двое из одной группы не сидят за столом рядом.

На бесконечной в обе стороны полосе из клеток, пронумерованных целыми числами, лежит несколько камней (возможно, по нескольку в одной клетке). Разрешается выполнять следующие действия:<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>k</i> вершин правильного <i>n</i>-угольника закрашены. Закраска называется <i>почти равномерной</i>, если для любого натурального <i>m</i> верно следующее условие: если <i>M</i>₁ – множество <i>m</i> расположенных подряд вершин и <i>M</i>₂ – другое такое множество, то количество закрашенных вершин в <i>M</i>₁ отличается от количества закрашенных вершин в <i>M</i>₂ не больше чем на 1. Доказать, что для любых натуральных <i>n</i> и  <i>k</i> ≤ <i>n</i>  почти равномерная закраска существует и что она единственна с точностью до поворотов закрашенного множест...

На химической конференции присутствовало<i>k</i>учёных химиков и алхимиков, причём химиков было больше, чем алхимиков. Известно, что на любой вопрос химики всегда отвечают правду, а алхимики иногда говорят правду, а иногда лгут. Оказавшийся на конференции математик про каждого учёного хочет установить, химик тот или алхимик. Для этого он любому учёному может задать вопрос: ``Кем является такой-то: химиком или алхимиком?'' (В частности, может спросить, кем является сам этот учёный.) Доказать, что математик может установить это за: а) 4<i>k</i>вопросов; б) 2<i>k</i>- 2 вопросов.

Прямоугольный лист бумаги размером<i>a</i>×<i>b</i>см разрезан на прямоугольные полоски, каждая из которых имеет сторону 1 см. Линии разрезов параллельны сторонам исходного листа. Доказать, что хотя бы одно из чисел<i>a</i>или<i>b</i>целое.

Окружность разбита точками<i>A</i>₁,<i>A</i>₂,...,<i>A</i>_<i>n</i>на<nobr><i>n</i> равных</nobr>дуг, каждая из которых окрашена в какой-то цвет. Две дуги окружности (с концами в точках разбиения) называем одинаково окрашенными, если при некотором повороте окружности одна из них полностью, включая цвета всех дуг, совпадает с другой. (Например, на рисунке дуги<i>A</i>₂<i>A</i>₆и<i>A</i>₆<i>A</i>₁₀одинаково окрашены.)Докажите, что если для каждой точки разбиения <i>A</i><sub><i>k</i><...

Предлагается построить<i>N</i>точек на плоскости так, чтобы все расстояния между ними равнялись заранее заданным числам: для любых двух точек<i>M</i>_<i>i</i>и<i>M</i>_<i>j</i>, где<i>i</i>и<nobr><i>j</i> —</nobr>любые числа<nobr>от 1</nobr><nobr>до <i>N</i>.</nobr>Можно ли провести построение, если расстояния <i>r</i>_<i>ij</i> заданы так, что всякие 5 из <i>N</i> точек построить можно? б) Достаточно ли требовать, чтобы можно было построить всякие 4 из <nobr><i>N</i> точек?</nobr> в) Что изменится, если строить точки не на плоскости, а...

На бесконечном клетчатом листе белой бумаги<i>n</i>клеток закрашены в чёрный цвет. В моменты времени<nobr><i>t</i> = 1,</nobr>2, 3,... происходит одновременное перекрашивание всех клеток листа по следующему правилу: каждая клетка<i>k</i>приобретает тот цвет, который имело в предыдущий момент большинство из трёх клеток: самой клетки<i>k</i>и её соседей справа и сверху (если две или три из этих клеток были белыми, то<i>k</i>становится белой, если две или три из них были чёрными,— то чёрной).а) Докажите, что через конечное время на листе не останется ни одной чёрной клетки. б) Докажите, что чёрные клетки исчезнут не позже, чем в момент времени <nobr><i>t</i> = <i>n</i>.</nobr>

а) Сумма длин рёбер любого выпуклого многогранника больше утроенного диаметра. Докажите это.<span class="prim">(Диаметром многогранника называют наибольшую из длин всевозможных отрезков с концами в вершинах многогранника.)</span>б) Для любых двух <nobr>вершин <i>A</i></nobr> <nobr>и <i>B</i></nobr> любого выпуклого многогранника существуют три ломаные, каждая из которых идёт по рёбрам многогранника <nobr>из <i>А</i></nobr> <nobr>в <i>В</i></nobr> и никакие две не проходят по одному ребру. Докажите это. в) Если в выпуклом многограннике разрезать два ребра, то для любых двух его <nobr>вершин <i>А</i></nobr> <nobr>и <i>В</i></nobr&g...

Все натуральные числа, в десятичной записи которых не больше<nobr><i>n</i> цифр,</nobr>разбили на два множества следующим образом. В первое множество входят числа с нечётной суммой цифр, а во<nobr>второе —</nobr>c чётной суммой цифр. Докажите, что для любого натурального числа<nobr><i>k</i> <font face="Symbol">£</font> <i>n</i></nobr>сумма<nobr><i>k</i>-х степеней</nobr>всех чисел первого множества равна сумме<nobr><i>k</i>-х степеней</nobr>всех чисел второго множества.

Пусть на двух пересекающихся прямых <i>l</i>₁и <i>l</i>₂выбраны точки <i>M</i>₁и <i>M</i>₂, не совпадающие с точкой пересечения <i>M</i>этих прямых. Поставим в соответствие им окружность, проходящую через <i>M</i>₁,<i>M</i>₂и <i>M</i>. Если (<i>l</i>₁,<i>M</i>₁), (<i>l</i>₂,<i>M</i>₂), (<i>l</i>₃,<i>M</i>₃) — прямые с выбранными точками в общем положении...

В этой задаче мы будем рассматривать наборы из <i>n</i>прямых общего положения, т. е. наборы, в которых никакие две прямые не параллельны и никакие три не проходят через одну точку. Набору из двух прямых общего положения поставим в соответствие точку — их точку пересечения, а набору из трех прямых общего положения — окружность, проходящую через три точки пересечения. Если <i>l</i>₁,<i>l</i>₂,<i>l</i>₃,<i>l</i>₄ — четыре прямые общего положения, то четыре окружности <i>S</i>_i, соответствующие четырем тройкам прямых, получаемых отбрасыванием прямой <i>l</i>_i, проходят через...