Олимпиадные задачи по теме «Принцип Дирихле» - сложность 4-5 с решениями
Принцип Дирихле
Назад30 учеников одного класса решили побывать друг у друга в гостях. Известно, что ученик за вечер может сделать несколько посещений, и что в тот вечер, когда к нему кто-нибудь должен прийти, он сам никуда не уходит. Покажите, что для того, чтобы все побывали в гостях у всех,
а) четырёх вечеров недостаточно,
б) пяти вечеров также недостаточно,
в) а десяти вечеров достаточно,
г) и даже семи вечеров тоже достаточно.
На прямоугольном листе бумаги нарисован круг, внутри которого Миша мысленно выбирает<i>n</i>точек, а Коля пытается их разгадать. За одну попытку Коля указывает на листе (внутри или вне круга) одну точку, а Миша сообщает Коле расстояние от нее до ближайшей неразгаданной точки. Если оно оказывается нулевым, то после этого указанная точка считается разгаданной. Коля умеет отмечать на листе точки, откладывать расстояния и производить построения циркулем и линейкой. Может ли Коля наверняка разгадать все выбранные точки менее, чем за (<i>n</i>+1)<sup>2</sup>попыток?
<i>X</i>и<i>Y</i>— два выпуклых многоугольника, причём многоугольник<i>X</i>содержится внутри<i>Y</i>. Пусть<i>S</i>(<i>X</i>) и<i>S</i>(<i>Y</i>) — площади этих многоугольников, а<i>P</i>(<i>X</i>) и<i>P</i>(<i>Y</i>) — их периметры. Доказать, что${\frac{S(X)}{P(X)}}$< 2<sup> . </sup>${\frac{S(Y)}{P(Y)}}$.
На плоскости проведено 3000 прямых, причём никакие две из них не параллельны и никакие три не пересекаются в одной точке. По этим прямым плоскость разрезана на куски. Доказать, что среди кусков найдётся не менее: а) 1000 треугольников, б) 2000 треугольников.
а) Доказать, что сумма цифр числа <i>K</i> не более чем в 8 раз превосходит сумму цифр числа 8<i>K</i>.
б) Для каких натуральных <i>k</i> существует такое положительное число <i>c<sub>k</sub></i>, что <img align="absmiddle" src="/storage/problem-media/78791/problem_78791_img_2.gif"> ≥ <i>c<sub>k</sub></i> для всех натуральных <i>N</i>? Найдите наибольшее подходящее значение <i>c<sub>k</sub></i>.
Посередине между двумя параллельными улицами стоят в один ряд одинаковые дома со стороной, равной <i>a</i>. Расстояние между улицами – 3<i>a</i>, а расстояние между двумя соседними домами – 2<i>a</i> (см. рис.). <div align="center"><img src="/storage/problem-media/78571/problem_78571_img_2.gif"></div>Одна улица патрулируется полицейскими, которые движутся на расстоянии 9<i>a</i> друг от друга со скоростью <i>v</i>. К тому времени, как первый полицейский проходит мимо середины некоторого дома, точно напротив него на другой улице появляется гангстер. С какой постоянной скоростью и в какую сторону должен двигаться по этой улице гангстер, чтобы ни один полицейский его не заметил?
Два неравных картонных диска разделены на 1965 равных секторов. На каждом из дисков произвольно выбраны 200 секторов и раскрашены в красный цвет. Меньший диск наложен на больший, так что их центры совпадают, а секторы целиком лежат один против другого. Меньший диск поворачивают на всевозможные углы, кратные${\frac{1}{1965}}$части окружности, оставляя больший диск неподвижным. Доказать, что по крайней мере при 60 положениях на дисках совпадут не более 20 красных секторов.
При дворе короля Артура собрались 2<i>n</i>рыцарей, причём каждый из них имеет среди присутствующих не более <i>n</i>– 1 врага. Доказать, что Мерлин, советник Артура, может так рассадить рыцарей за круглым столом, что ни один из них не будет сидеть рядом со своим врагом.
Доказать, что на сфере нельзя так расположить три дуги больших окружностей в300<sup><tt>o</tt></sup>каждая, чтобы никакие две из них не имели ни общих точек, ни общих концов. <i>Примечание</i>: Большая окружность – это окружность, полученная в сечении сферы плоскостью, проходящей через ее центр.
В квадрате со стороной 100 расположено<i>N</i>кругов радиуса 1, причём всякий отрезок длины 10, целиком расположенный внутри квадрата, пересекает хотя бы один круг. Доказать, что<i>N</i>$\ge$400.<i>Примечание Problems.Ru</i>: Рассматриваются <i>открытые</i> круги, то есть круги без ограничивающей их окружности.
Автобусный маршрут содержит 14 остановок (считая две конечные). В автобусе одновременно могут ехать не более 25 пассажиров. Доказать, что во время поездки автобуса из одного конца в другой
a) найдутся восемь таких различных остановок <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</i><sub>3</sub>, <i>B</i><sub>3</sub>, <i>A</i><sub>4</sub>, <i>B</i><sub>4</sub>, что ни один пассажир не едет от <i>A</i><sub>1</sub> до <i>B</i><sub>1</sub>, ни один пассажир не едет от <i>A</i><sub>2</su...
Числа 1, 2, 3, ..., 101 выписаны в ряд в каком-то порядке.
Докажите, что из них можно вычеркнуть 90 так, что оставшиеся 11 будут расположены по их величине (либо возрастая, либо убывая).
Докажите, что числа вида 2<sup>n</sup>при различных целых положительных<i>n</i>могут начинаться на любую наперёд заданную комбинацию цифр.
Для каких <i>n</i> существует такая замкнутая несамопересекающаяся ломаная из <i>n</i> звеньев, что каждая прямая, содержащая одно из звеньев этой ломаной, содержит ещё хотя бы одно её звено?
На окружности расположено множество<nobr><i>F</i> точек,</nobr>состоящее из<nobr>100 дуг.</nobr>При любом<nobr>повороте <i>R</i></nobr>окружности множество<i>R</i>(<i>F</i>) имеет хотя бы одну общую точку с<nobr>множеством <i>F</i>.</nobr><span class="prim">(Другими словами, для любого <nobr>угла α</nobr> <nobr>от 0°</nobr> <nobr>до 180°</nobr> в <nobr>множестве <i>F</i></nobr> можно указать две точки, отстоящие одна от другой на <nobr>угол α.)</nobr></span>Какую наименьшую сумму длин могут иметь<nobr>100 дуг,</nobr>образующих<nobr>множество <i>F</i>?</nobr&g...
На прямой дано 50 отрезков. Докажите, что верно хотя бы одно из следующих утверждений:<ul class="zad"><li>некоторые 8 из этих отрезков имеют общую точку; </li><li>некоторые 8 из этих отрезков таковы, что никакие два из них не пересекаются.</li></ul>
Каждая из девяти прямых разбивает квадрат на два четырёхугольника, площади которых относятся как<nobr>2 : 3.</nobr>Докажите, что по крайней мере три из этих девяти прямых проходят через одну точку.
На плоскости нарисованы неравнобедренный треугольник <i>ABC</i> и вписанная в него окружность ω. Пользуясь только линейкой и проведя не более восьми линий, постройте на ω такие точки <i>A′, B′, C′</i>, что лучи <i>B′C′, C′A′, A′B′</i> проходят через <i>A, B, C</i> соответственно.
На доске выписаны в ряд <i>n</i> положительных чисел <i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>, ..., <i>a<sub>n</sub></i>. Вася хочет выписать под каждым числом <i>a<sub>i</sub></i> число <i>b<sub>i</sub> ≥ a<sub>i</sub></i> так, чтобы для каждых двух из чисел <i>b</i><sub>1</sub>, <i>b</i><sub>2</sub>, ..., <i>b<sub>n</sub></i> отношение одного из них к другому было целым. Докажите, что Вася может выписать требуемые числа так, чтобы выполнялось неравенство <i>b</i><sub>1</sub><i>b</i><sub>2</sub>...<i>b<sub>n</...
Даны натуральные числа <i>a</i> и <i>b</i>, причём <i>a < b</i> < 2<i>a</i>. На клетчатой плоскости отмечены некоторые клетки так, что в каждом клетчатом прямоугольнике <i>a</i>×<i>b</i> или <i>b</i>×<i>a</i> есть хотя бы одна отмеченная клетка. При каком наибольшем α можно утверждать, что для любого натурального <i>N</i> найдётся клетчатый квадрат <i>N</i>×<i>N</i>, в котором отмечено хотя бы α<i>N</i>² клеток?
На поверхности сферической планеты расположены четыре материка, отделённые друг от друга океаном. Назовем точку океана <i>особой</i>, если для нее найдутся не менее трёх ближайших (находящихся от нее на равных расстояниях) точек суши, причём все на разных материках. Какое наибольшее число особых точек может быть на этой планете?
Двое игроков играют в карточную игру. У них есть колода из <i>n</i> попарно различных карт. Про любые две карты из колоды известно, какая из них бьёт другую (при этом, если <i>A</i> бьёт <i>B</i>, а <i>B</i> бьёт <i>C</i>, то может оказаться, что <i>C</i> бьёт <i>A</i>). Колода распределена между игроками произвольным образом. На каждом ходу игроки открывают по верхней карте из своих колод, и тот, чья карта бьёт карту другого игрока, берёт обе карты и кладёт их в самый низ своей колоды в произвольном порядке по своему усмотрению. Докажите, что при любой исходной раздаче игроки могут, зная расположение карт, договориться и действовать так, чтобы один из игроков остался без карт.
На плоскости дано <i>n</i> выпуклых попарно пересекающихся <i>k</i>-угольников. Каждый из них можно перевести в любой другой гомотетией с положительным коэффициентом. Докажите, что на плоскости найдётся точка, принадлежащая хотя бы <img align="absmiddle" src="/storage/problem-media/64776/problem_64776_img_2.gif"> из этих <i>k</i>-угольников.
В государстве <i>n</i> городов, и между каждыми двумя из них курсирует экспресс (в обе стороны). Для каждого экспресса цены билетов "туда" и "обратно" равны, а для разных экспрессов эти цены различны. Докажите, что путешественник может выбрать начальный город, выехать из него и проехать последовательно на <i>n</i> – 1 экспрессах, платя за проезд на каждом следующем меньше, чем за проезд на предыдущем. (Путешественник может попадать несколько раз в один и тот же город.)
а) Можно ли квадрат6×6 замостить костями домино1×2 так, чтобы не было к швак, т. е. прямой, не разрезающей костей? б) Докажите, что любой прямоугольник<i>m</i>×<i>n</i>, где<i>m</i>и<i>n</i>больше 6 и<i>mn</i>четно, можно замостить костями домино так, чтобы не было к швак. в) Докажите, что прямоугольник6×8 можно замостить костями домино так, чтобы не было к швак.