Олимпиадные задачи по теме «Принцип Дирихле» для 1-8 класса - сложность 4 с решениями
Принцип Дирихле
НазадДве команды шахматистов одинаковой численности сыграли матч: каждый сыграл по одному разу с каждым из другой команды. В каждой партии давали 1 очко за победу, ½ – за ничью и 0 – за поражение. В итоге команды набрали поровну очков. Докажите, что какие-то два участника матча тоже набрали поровну очков, если в обеих командах было:
а) по 5 шахматистов;
б) произвольное равное число шахматистов.
Какое минимальное количество клеток можно закрасить черным в белом квадрате 300×300, чтобы никакие три черные клетки не образовывали уголок, а после закрашивания любой белой клетки это условие нарушалось?
Найдите наибольшее натуральное число <i>N</i>, для которого при произвольной расстановке различных натуральных чисел от 1 до 400 в клетках квадратной таблицы 20×20 найдутся два числа, стоящих в одной строке или одном столбце, разность которых будет не меньше <i>N</i>.
Клетки таблицы 100×100 окрашены в 4 цвета так, что в каждой строке и в каждом столбце ровно по 25 клеток каждого цвета.
Докажите, что найдутся две строки и два столбца, все четыре клетки на пересечении которых окрашены в разные цвета.
В клетках таблицы 10×10 расставлены числа 1, 2, 3, ..., 100 так, что сумма любых двух соседних чисел не превосходит <i>S</i>.
Найдите наименьшее возможное значение <i>S</i>. (Числа называются соседними, если они стоят в клетках, имеющих общую сторону.)
В однокруговом футбольном турнире играли  <i>n</i> > 4 команд. За победу давалось 3 очка, за ничью 1, за проигрыш 0. Оказалось, что все команды набрали поровну очков.
а) Докажите, что найдутся четыре команды, имеющие поровну побед, поровну ничьих и поровну поражений.
б) При каком наименьшем <i>n</i> могут не найтись пять таких команд?
У ведущего есть колода из 52 карт. Зрители хотят узнать, в каком порядке лежат карты (при этом не уточняя сверху вниз или снизу вверх). Разрешается задавать ведущему вопросы вида "Сколько карт лежит между такой-то и такой-то картами?". Один из зрителей подсмотрел, в каком порядке лежат карты. Какое наименьшее число вопросов он должен задать, чтобы остальные зрители по ответам на эти вопросы могли узнать порядок карт в колоде?
На пол положили правильный треугольник<i>ABC</i>, выпиленный из фанеры. В пол вбили три гвоздя (по одному вплотную к каждой стороне треугольника) так, что треугольник невозможно повернуть, не отрывая от пола. Первый гвоздь делит сторону<i>AB</i>в отношении 1 : 3, считая от вершины<i>A</i>, второй делит сторону<i>BC</i>в отношении 2 : 1, считая от вершины<i>B</i>. В каком отношении делит сторону<i>AC</i>третий гвоздь?
Петя разрезал прямоугольный лист бумаги по прямой. Затем он разрезал по прямой один из получившихся кусков. Затем он проделал то же самое с одним из трёх получившихся кусков и т.д. Докажите, что после достаточного количества разрезаний можно будет выбрать среди получившихся кусков 100 многоугольников с одинаковым числом вершин (например, 100 треугольников или 100 четырёхугольников и т.д.).
Дима придумал секретный шифр: каждая буква заменяется на слово длиной не больше 10 букв. Шифр называется <i>хорошим</i>, если всякое зашифрованное слово расшифровывается однозначно. Серёжа убедился (с помощью компьютера), что если зашифровать слово длиной не больше 10000 букв, то результат расшифровывается однозначно. Следует ли из этого, что шифр хороший? (В алфавите 33 буквы, под "словом" мы понимаем любую последовательность букв, независимо от того, имеет ли она смысл.)
В таблице из <i>n</i> столбцов и 2<sup><i>n</i></sup> строк, в которых выписаны все возможные различные наборы из <i>n</i> чисел 1 и –1, некоторые числа заменены нулями. Докажите, что можно выбрать некоторое непустое подмножество строк так, что:
а) сумма всех чисел в выбранных строках равна 0;
б) сумма всех выбранных строк есть нулевая строка.
(Строки складываются покоординатно как векторы.)
30 учеников одного класса решили побывать друг у друга в гостях. Известно, что ученик за вечер может сделать несколько посещений, и что в тот вечер, когда к нему кто-нибудь должен прийти, он сам никуда не уходит. Покажите, что для того, чтобы все побывали в гостях у всех,
а) четырёх вечеров недостаточно,
б) пяти вечеров также недостаточно,
в) а десяти вечеров достаточно,
г) и даже семи вечеров тоже достаточно.
Посередине между двумя параллельными улицами стоят в один ряд одинаковые дома со стороной, равной <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 красных секторов.
В квадрате со стороной 100 расположено<i>N</i>кругов радиуса 1, причём всякий отрезок длины 10, целиком расположенный внутри квадрата, пересекает хотя бы один круг. Доказать, что<i>N</i>$\ge$400.<i>Примечание Problems.Ru</i>: Рассматриваются <i>открытые</i> круги, то есть круги без ограничивающей их окружности.
Числа 1, 2, 3, ..., 101 выписаны в ряд в каком-то порядке.
Докажите, что из них можно вычеркнуть 90 так, что оставшиеся 11 будут расположены по их величине (либо возрастая, либо убывая).
Для каких <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...
Каждая из девяти прямых разбивает квадрат на два четырёхугольника, площади которых относятся как<nobr>2 : 3.</nobr>Докажите, что по крайней мере три из этих девяти прямых проходят через одну точку.
В государстве <i>n</i> городов, и между каждыми двумя из них курсирует экспресс (в обе стороны). Для каждого экспресса цены билетов "туда" и "обратно" равны, а для разных экспрессов эти цены различны. Докажите, что путешественник может выбрать начальный город, выехать из него и проехать последовательно на <i>n</i> – 1 экспрессах, платя за проезд на каждом следующем меньше, чем за проезд на предыдущем. (Путешественник может попадать несколько раз в один и тот же город.)
Отрезок длиной 1 покрыт несколькими лежащими на нем отрезками. Докажите, что среди них можно выбрать несколько попарно непересекающихся отрезков, сумма длин которых не меньше 0,5.
Назовем крестом фигуру, образованную диагоналями квадрата со стороной 1 (рис.). Докажите, что в круге радиуса 100 можно разместить лишь конечное число непересекающихся крестов. <div align="center"><img src="/storage/problem-media/58103/problem_58103_img_2.gif" border="1"></div>
Дана бесконечная клетчатая бумага и фигура, площадь которой меньше площади клетки. Докажите, что эту фигуру можно положить на бумагу, не накрыв ни одной вершины клетки.
На отрезке длиной 1 закрашено несколько отрезков, причем расстояние между любыми двумя закрашенными точками не равно 0, 1. Докажите, что сумма длин закрашенных отрезков не превосходит 0, 5.
Внутри окружности радиуса <i>n</i>расположено 4<i>n</i>отрезков длиной 1. Докажите, что можно провести прямую, параллельную или перпендикулярную данной прямой <i>l</i>и пересекающую по крайней мере два данных отрезка.