Олимпиадные задачи по теме «Принцип крайнего» - сложность 4-5 с решениями

Оля и Максим оплатили путешествие по архипелагу из 2009 островов, где некоторые острова связаны двусторонними маршрутами катера. Они путешествуют, играя. Сначала Оля выбирает остров, на который они прилетают. Затем они путешествуют вместе на катерах, по очереди выбирая остров, на котором еще не были (первый раз выбирает Максим). Кто не сможет выбрать остров, проиграл. Докажите, что Оля может выиграть.

За круглым столом заседают <i>N</i> рыцарей. Каждое утро чародей Мерлин сажает их в другом порядке. Начиная со второго дня Мерлин разрешил рыцарям делать в течение дня сколько угодно пересадок такого вида: два сидящих рядом рыцаря меняются местами, если только они не были соседями в первый день. Рыцари стараются сесть в том же порядке, что и в какой-нибудь из предыдущих дней: тогда заседания прекратятся. Какое наибольшее число дней Мерлин гарантированно может проводить заседания?

(Рассадки, получающиеся друг из друга поворотом, считаются одинаковыми. Мерлин за столом не сидит.)

На плоскости отметили 4<i>n</i> точек, после чего соединили отрезками все пары точек, расстояние между которыми равно 1 см. Оказалось, что среди любых  <i>n</i> + 1  точек обязательно есть две, соединённые отрезком. Докажите, что всего проведено не менее 7<i>n</i> отрезков.

На плоскости отмечены все точки с целыми координатами (<i>x,y</i>)такие, что<i> x²+y²<img align="absmiddle" src="/storage/problem-media/115399/problem_115399_img_2.gif"> </i>10<i></i>10. Двое играют в игру (ходят по очереди). Первым ходом первый игрок ставит фишку в какую-то отмеченную точку и стирает ее. Затем каждым очередным ходом игрок переносит фишку в какую-то другую отмеченную точку и стирает ее. При этом длины ходов должны все время увеличиваться; кроме того, запрещено делать ход из точки в симметричную ей относительно центра. Проигрывает тот, кто не может сделать ход. Кто из играющих может обеспечить себе победу, как бы ни играл его соперник?

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

В стране есть <i>N</i> городов. Некоторые пары из них соединены беспосадочными двусторонними авиалиниями. Оказалось, что для любого <i>k</i>  (2 ≤ <i>k ≤ N</i>)  при любом выборе <i>k</i> городов количество авиалиний между этими городами не будет превосходить  2<i>k</i> – 2.  Докажите, что все авиалинии можно распределить между двумя авиакомпаниями так, что не будет замкнутого авиамаршрута, в котором все авиалинии принадлежат одной компании.

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

Пусть<i> h </i> — наименьшая высота тетраэдра,<i> d </i> — наименьшее расстояние между его противоположными ребрами. При каких<i> t </i>возможно неравенство<i> d>th </i>?

В треугольнике провели серединные перпендикуляры к его сторонам и измерили их отрезки, лежащие внутри треугольника.

  а) Все три отрезка оказались равны. Верно ли, что треугольник равносторонний?

  б) Два отрезка оказались равны. Верно ли, что треугольник равнобедренный?

  в) Могут ли длины отрезков равняться 4, 4 и 3?

Докажите, что для треугольника со сторонами<i> a </i>,<i> b </i>,<i> c </i>и площадью<i> S </i>выполнено неравенство <center><i>

a²+b²+c²-<img src="/storage/problem-media/111723/problem_111723_img_2.gif"> </i>(<i>|a-b|+|b-c|+|c-a|</i>)<i>²<img src="/storage/problem-media/111723/problem_111723_img_3.gif"> </i>4<i><img src="/storage/problem-media/111723/problem_111723_img_4.gif"> S.

</i></center>

Среди вершин любого ли многогранника можно выбрать четыре вершины тетраэдра, площадь проекции которого на любую плоскость составляет от площади проекции (на ту же плоскость) исходного многогранника: а) больше, чем<i> <img src="/storage/problem-media/111351/problem_111351_img_2.gif"> </i>, б) не меньше, чем<i> <img src="/storage/problem-media/111351/problem_111351_img_3.gif"> </i>, в) не меньше, чем<i> <img src="/storage/problem-media/111351/problem_111351_img_4.gif"> </i>?

На плоскости даны точки<i> A₁ </i>,<i> A₂ </i>,<i> A_n </i>и точки<i> B₁ </i>,<i> B₂ </i>,<i> B_n </i>. Докажите, что точки<i> B_i </i>можно перенумеровать так, что для всех<i> i<img src="/storage/problem-media/110807/problem_110807_img_2.gif"> j </i>угол между векторами<i> <img src="/storage/problem-media/110807/problem_110807_img_3.gif"> </i>и<i> <img src="/storage/problem-media/110807/problem_110807_img_4.gif"> </i>– острый или прямой.

Определите наименьшее действительное число <i>M</i>, при котором неравенство   |<i>ab</i>(<i>a</i>² – <i>b</i>²) + <i>bc</i>(<i>b</i>² – <i>c</i>²) + <i>ca</i>(<i>c</i>² – <i>a</i>²)| ≤ <i>M</i>(<i>a</i>² + <i>b</i>² + <i>c</i>²)²   выполняется для любых действительных чисел <i>a, b, c</i>.

Диагональ правильного 2006-угольника <i>P</i> называется <i>хорошей</i>, если её концы делят границу <i>P</i> на две части, каждая из которых содержит нечётное число сторон. Стороны <i>P</i> также называются хорошими. Пусть <i>P</i> разбивается на треугольники 2003 диагоналями, никакие две из которых не имеют общих точек внутри <i>P</i>. Какое наибольшее число равнобедренных треугольников, каждый из которых имеет две хорошие стороны, может иметь такое разбиение?

Некоторые участники олимпиады дружат, и дружба взаимна. Назовём группу участников <i>кликой</i>, если все они дружат между собой. Их число называется <i>размером</i> клики. Известно, что максимальный размер клики чётен. Докажите, что участников можно рассадить по двум аудиториям так, что максимальные размеры клик в обеих аудиториях совпадают.

а) В 99 ящиках лежат яблоки и апельсины.

Докажите, что можно так выбрать 50 ящиков, что в них окажется не менее половины всех яблок и не менее половины всех апельсинов. б) В 100 ящиках лежат яблоки и апельсины.

Докажите, что можно так выбрать 34 ящика, что в них окажется не менее трети всех яблок и не менее трети всех апельсинов.

В 100 ящиках лежат яблоки, апельсины и бананы. Докажите, что можно так выбрать 51 ящик, что в них окажется не менее половины всех яблок, не менее половины всех апельсинов и не менее половины всех бананов.

На плоскости отмечено<i> N<img src="/storage/problem-media/110154/problem_110154_img_2.gif"> </i>3различных точек. Известно, что среди попарных расстояний между отмеченными точками встречаются не более<i> n </i>различных расстояний. Докажите, что<i> N<img src="/storage/problem-media/110154/problem_110154_img_3.gif"> </i>(<i>n+</i>1)<i>² </i>.

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

Каждая клетка клетчатой плоскости раскрашена в один из<i>n</i>² цветов так, что в каждом квадрате из<i>n×</i>клеток встречаются все цвета. Известно, что в какой-то строке встречаются все цвета. Докажите, что существует столбец, раскрашенный ровно в<i>n</i>цветов.

Докажите, что из любого конечного множества точек на плоскости можно так удалить одну точку, что оставшееся множество можно разбить на две части меньшего диаметра. (Диаметр – это максимальное расстояние между точками множества.)

Имеется 8 монет, 7 из которых – настоящие, которые весят одинаково, и одна фальшивая, отличающаяся по весу от остальных. Чашечные весы без гирь таковы, что если положить на их чашки равные грузы, то любая из чашек может перевесить, если же грузы различны по массе, то обязательно перетягивает чашка с более тяжелым грузом. Как за четыре взвешивания наверняка определить фальшивую монету и установить, легче она или тяжелее остальных?

На плоскости рассматривается конечное множество равных, параллельно расположенных квадратов, причем среди любых<i> k+</i>1квадратов найдутся два пересекающихся. Докажите, что это множество можно разбить не более чем на2<i>k-</i>1непустых подмножеств так, что в каждом подмножестве все квадраты будут иметь общую точку.

Натуральные числа от 1 до 100 расставлены по кругу в таком порядке, что каждое число либо больше обоих соседей, либо меньше обоих соседей. Пара соседних чисел называется <i>хорошей</i>, если при выкидывании этой пары вышеописанное свойство сохраняется. Какое минимальное количество хороших пар может быть?

В кабинете президента стоят 2004 телефона, любые два из которых соединены проводом одного из четырёх цветов. Известно, что провода всех четырёх цветов присутствуют. Всегда ли можно выбрать несколько телефонов так, чтобы среди соединяющих их проводов встречались провода ровно трех цветов?