Олимпиадные задачи по математике для 4-11 класса
В некотором городе сеть автобусных маршрутов устроена так, что каждые два маршрута имеют ровно одну общую остановку, и на каждом маршруте есть хотя бы 4 остановки. Докажите, что все остановки можно распределить между двумя компаниями так, что на каждом маршруте найдутся остановки обеих компаний.
Назовём компанию <i>k-неразбиваемой</i>, если при любом разбиении её на <i>k</i> групп в одной из групп найдутся два знакомых человека. Дана 3-неразбиваемая компания, в которой нет четырёх попарно знакомых человек. Докажите, что её можно разделить на две компании, одна из которых 2-неразбиваемая, а другая – 1-неразбиваемая.
В королевстве <i>N</i> городов, некоторые пары которых соединены непересекающимися дорогами с двусторонним движением (города из такой пары называются <i>соседними</i>). При этом известно, что из каждого города можно доехать до любого другого, но невозможно, выехав из некоторого города и двигаясь по различным дорогам, вернуться в исходный город.
Однажды Король провел такую реформу: каждый из <i>N</i> мэров городов стал снова мэром одного из <i>N</i> городов, но, возможно, не того города, в котором он работал до реформы. Оказалось, что каждые два мэра, работавшие в соседних городах до реформы, оказались в соседних городах и после реформы. Докажите, что либо найдётся город, в котором мэр после реформы не поменялся, либо найдётся пара сос...
На плоскости отмечено<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><sup>2</sup> </i>.
На плоскости расположено[<i><img src="/storage/problem-media/110102/problem_110102_img_2.gif"> n</i>]прямоугольников со сторонами, параллельными осям координат. Известно, что любой прямоугольник пересекается хотя бы с<i> n </i>прямоугольниками. Доказать, что найдется прямоугольник, пересекающийся со всеми прямоугольниками.
В выпуклом многоугольнике на плоскости содержится не меньше <i>m</i>² + 1 точек с целыми координатами.
Докажите, что в нём найдутся <i>m</i> + 1 точек с целыми координатами, которые лежат на одной прямой.
В стране 2000 городов, некоторые пары городов соединены дорогами. Известно, что через любой город проходит не более <i>N</i> различных несамопересекающихся циклических маршрутов нечётной длины. Докажите, что страну можно разделить на 2<i>N</i> + 2 республики так, чтобы никакие два города из одной республики не были соединены дорогой.
В стране 2000 городов, некоторые пары городов соединены дорогами. Известно, что через любой город проходит не более <i>N</i> различных несамопересекающихся циклических маршрутов нечётной длины. Докажите, что страну можно разделить на <i>N</i> + 2 республики так, чтобы никакие два города из одной республики не были соединены дорогой.
Каждый голосующий на выборах вносит в избирательный бюллетень фамилии<i> n </i>кандидатов. На избирательном участке находится<i> n+</i>1урна. После выборов выяснилось, что в каждой урне лежит по крайней мере один бюллетень и при всяком выборе(<i>n+</i>1)-го бюллетеня по одному из каждой урны найдется кандидат, фамилия которого встречается в каждом из выбранных бюллетеней. Докажите, что по крайней мере в одной урне все бюллетени содержат фамилию одного и того же кандидата.
В пространстве даны<i> n </i>точек общего положения (никакие три не лежат на одной прямой, никакие четыре не лежат в одной плоскости). Через каждые три из них проведена плоскость. Докажите, что какие бы<i> n-</i>3точки в пространстве ни взять, найдется плоскость из проведенных, не содержащая ни одной из этих<i> n-</i>3точек.
На плоскости дано множество из<i> n<img src="/storage/problem-media/109961/problem_109961_img_2.gif"></i>9точек. Для любых 9 его точек можно выбрать две окружности так, что все эти точки окажутся на выбранных окружностях. Докажите, что все<i> n </i>точек лежат на двух окружностях.
Докажите, что из любого конечного множества точек на плоскости можно так удалить одну точку, что оставшееся множество можно разбить на две части меньшего диаметра. (Диаметр – это максимальное расстояние между точками множества.)
Обозначим через <i>S</i>(<i>m</i>) сумму цифр натурального числа <i>m</i>. Докажите, что существует бесконечно много таких натуральных <i>n</i>, что <i>S</i>(3<i><sup>n</sup></i>) ≥ <i>S</i>(3<sup><i>n</i>+1</sup>).
В каждой клетке квадратной таблицы размером <i>n×n</i> клеток (<i>n</i> ≥ 3) записано число 1 или –1. Если взять любые две строки, перемножить числа, стоящие в них друг над другом и сложить <i>n</i> получившихся произведений, то сумма будет равна 0. Докажите, что число <i>n</i> делится на 4.
Длина наибольшей стороны треугольника равна 1. Докажите, что три круга радиуса<i> <img src="/storage/problem-media/109880/problem_109880_img_2.gif"> </i>с центрами в вершинах покрывают весь треугольник.
На плоскости рассматривается конечное множество равных, параллельно расположенных квадратов, причем среди любых<i> k+</i>1квадратов найдутся два пересекающихся. Докажите, что это множество можно разбить не более чем на2<i>k-</i>1непустых подмножеств так, что в каждом подмножестве все квадраты будут иметь общую точку.
Треугольник<i> T </i>содержится внутри выпуклого центрально-симметричного многоугольника<i> M </i>. Треугольник<i> T' </i>получается из треугольника<i> T </i>центральной симметрией относительно некоторой точки<i> P </i>, лежащей внутри треугольника<i> T </i>. Докажите, что хотя бы одна из вершин треугольника<i> T' </i>лежит внутри или на границе многоугольника<i> M </i>.
В стране несколько городов, некоторые пары городов соединены двусторонними беспосадочными авиалиниями, принадлежащими <i> k </i> авиакомпаниям. Известно, что каждые две линии одной авиакомпании имеют общий конец. Докажите, что все города можно разбить на <i>k</i> + 2 группы так, что никакие два города из одной группы не соединены авиалинией.
На прямой расположены2<i>k-</i>1белый и2<i>k-</i>1черный отрезок. Известно, что любой белый отрезок пересекается хотя бы с<i> k </i>черными, а любой черный – хотя бы с<i> k </i>белыми. Докажите, что найдутся черный отрезок, пересекающийся со всеми белыми, и белый отрезок, пересекающийся со всеми черными.
На плоскости дано конечное множество точек<i> X </i>и правильный треугольник<i> T </i>. Известно, что любое подмножество<i> X' </i>множества<i> X </i>, состоящее из не более9точек, можно покрыть двумя параллельными переносами треугольника<i> T </i>. Докажите, что все множество<i> X </i>можно покрыть двумя параллельными переносами<i> T </i>.
Дано дерево с <i>n</i> вершинами, <i>n</i> ≥ 2. В его вершинах расставлены числа <i>x</i><sub>1</sub>, <i>x</i><sub>2</sub>, <i>x<sub>n</sub></i>, а на каждом ребре записано произведение чисел, стоящих в концах этого ребра. Обозначим через <i>S</i> сумму чисел на всех рёбрах. Докажите, что <img align="absmiddle" src="/storage/problem-media/109782/problem_109782_img_2.gif">
На плоскости взято конечное число красных и синих прямых, среди которых нет параллельных, так, что через каждую точку пересечения одноцветных прямых проходит прямая другого цвета. Докажите, что все прямые проходят через одну точку.
В стране 2001 город, некоторые пары городов соединены дорогами, причём из каждого города выходит хотя бы одна дорога и нет города, соединённого дорогами со всеми остальными. Назовём множество городов <i>D доминирующим</i>, если каждый не входящий в <i>D</i> город соединён дорогой с одним из городов множества <i>D</i>. Известно, что в каждом доминирующем множестве хотя бы <i>k</i> городов. Докажите, что страну можно разбить на 2001 – <i>k</i> республик так, что никакие два города из одной республики не будут соединены дорогой.
На плоскости даны два таких конечных набора<i> P<sub>1</sub> </i>и<i> P<sub>2</sub> </i>выпуклых многоугольников, что любые два многоугольника из разных наборов имеют общую точку и в каждом из двух наборов<i> P<sub>1</sub> </i>и<i> P<sub>2</sub> </i>есть пара непересекающихся многоугольников. Докажите, что существует прямая, пересекающая все многоугольники обоих наборов.
На прямоугольном столе лежат равные картонные квадраты<i> n </i>различных цветов со сторонами, параллельными сторонам стола. Если рассмотреть любые<i> n </i>квадратов различных цветов, то какие-нибудь два из них можно прибить к столу одним гвоздем. Докажите, что все квадраты некоторого цвета можно прибить к столу2<i>n-</i>2гвоздями.