Найдите задачу для урока, кружка или самостоятельной работы.
В некотором городе сеть автобусных маршрутов устроена так, что каждые два маршрута имеют ровно одну общую остановку, и на каждом маршруте есть хотя бы 4 остановки. Докажите, что все остановки можно распределить между двумя компаниями так, что на каждом маршруте найдутся остановки обеих компаний.
Назовём компанию k-неразбиваемой, если при любом разбиении её на k групп в одной из групп найдутся два знакомых человека. Дана 3-неразбиваемая компания, в которой нет четырёх попарно знакомых человек. Докажите, что её можно разделить на две компании, одна из которых 2-неразбиваемая, а другая – 1-неразбиваемая.
В королевстве N городов, некоторые пары которых соединены непересекающимися дорогами с двусторонним движением (города из такой пары называются соседними). При этом известно, что из каждого города можно доехать до любого другого, но невозможно, выехав из некоторого города и двигаясь по различным дорогам, вернуться в исходный город. Однажды Король провел такую реформу: каждый из N мэров городов стал снова мэром одного из N городов, но, возможно, не того города, в котором он работал до реформы. Оказалось, что каждые два мэра, работавшие в соседних городах до реформы, оказались в соседних городах...
На плоскости отмечено N 3различных точек. Известно, что среди попарных расстояний между отмеченными точками встречаются не более n различных расстояний. Докажите, что N (n+1)2 .
На плоскости расположено[ n]прямоугольников со сторонами, параллельными осям координат. Известно, что любой прямоугольник пересекается хотя бы с n прямоугольниками. Доказать, что найдется прямоугольник, пересекающийся со всеми прямоугольниками.
В выпуклом многоугольнике на плоскости содержится не меньше m² + 1 точек с целыми координатами. Докажите, что в нём найдутся m + 1 точек с целыми координатами, которые лежат на одной прямой.
В стране 2000 городов, некоторые пары городов соединены дорогами. Известно, что через любой город проходит не более N различных несамопересекающихся циклических маршрутов нечётной длины. Докажите, что страну можно разделить на 2N + 2 республики так, чтобы никакие два города из одной республики не были соединены дорогой.
В стране 2000 городов, некоторые пары городов соединены дорогами. Известно, что через любой город проходит не более N различных несамопересекающихся циклических маршрутов нечётной длины. Докажите, что страну можно разделить на N + 2 республики так, чтобы никакие два города из одной республики не были соединены дорогой.
Каждый голосующий на выборах вносит в избирательный бюллетень фамилии n кандидатов. На избирательном участке находится n+1урна. После выборов выяснилось, что в каждой урне лежит по крайней мере один бюллетень и при всяком выборе(n+1)-го бюллетеня по одному из каждой урны найдется кандидат, фамилия которого встречается в каждом из выбранных бюллетеней. Докажите, что по крайней мере в одной урне все бюллетени содержат фамилию одного и того же кандидата.
В пространстве даны n точек общего положения (никакие три не лежат на одной прямой, никакие четыре не лежат в одной плоскости). Через каждые три из них проведена плоскость. Докажите, что какие бы n-3точки в пространстве ни взять, найдется плоскость из проведенных, не содержащая ни одной из этих n-3точек.
На плоскости дано множество из n9точек. Для любых 9 его точек можно выбрать две окружности так, что все эти точки окажутся на выбранных окружностях. Докажите, что все n точек лежат на двух окружностях.
Докажите, что из любого конечного множества точек на плоскости можно так удалить одну точку, что оставшееся множество можно разбить на две части меньшего диаметра. (Диаметр – это максимальное расстояние между точками множества.)
Обозначим через S(m) сумму цифр натурального числа m. Докажите, что существует бесконечно много таких натуральных n, что S(3n) ≥ S(3n+1).
В каждой клетке квадратной таблицы размером n×n клеток (n ≥ 3) записано число 1 или –1. Если взять любые две строки, перемножить числа, стоящие в них друг над другом и сложить n получившихся произведений, то сумма будет равна 0. Докажите, что число n делится на 4.
Длина наибольшей стороны треугольника равна 1. Докажите, что три круга радиуса с центрами в вершинах покрывают весь треугольник.
На плоскости рассматривается конечное множество равных, параллельно расположенных квадратов, причем среди любых k+1квадратов найдутся два пересекающихся. Докажите, что это множество можно разбить не более чем на2k-1непустых подмножеств так, что в каждом подмножестве все квадраты будут иметь общую точку.
Треугольник T содержится внутри выпуклого центрально-симметричного многоугольника M . Треугольник T' получается из треугольника T центральной симметрией относительно некоторой точки P , лежащей внутри треугольника T . Докажите, что хотя бы одна из вершин треугольника T' лежит внутри или на границе многоугольника M .
В стране несколько городов, некоторые пары городов соединены двусторонними беспосадочными авиалиниями, принадлежащими k авиакомпаниям. Известно, что каждые две линии одной авиакомпании имеют общий конец. Докажите, что все города можно разбить на k + 2 группы так, что никакие два города из одной группы не соединены авиалинией.
На прямой расположены2k-1белый и2k-1черный отрезок. Известно, что любой белый отрезок пересекается хотя бы с k черными, а любой черный – хотя бы с k белыми. Докажите, что найдутся черный отрезок, пересекающийся со всеми белыми, и белый отрезок, пересекающийся со всеми черными.
На плоскости дано конечное множество точек X и правильный треугольник T . Известно, что любое подмножество X' множества X , состоящее из не более9точек, можно покрыть двумя параллельными переносами треугольника T . Докажите, что все множество X можно покрыть двумя параллельными переносами T .
Дано дерево с n вершинами, n ≥ 2. В его вершинах расставлены числа x1, x2, xn, а на каждом ребре записано произведение чисел, стоящих в концах этого ребра. Обозначим через S сумму чисел на всех рёбрах. Докажите, что
На плоскости взято конечное число красных и синих прямых, среди которых нет параллельных, так, что через каждую точку пересечения одноцветных прямых проходит прямая другого цвета. Докажите, что все прямые проходят через одну точку.
В стране 2001 город, некоторые пары городов соединены дорогами, причём из каждого города выходит хотя бы одна дорога и нет города, соединённого дорогами со всеми остальными. Назовём множество городов D доминирующим, если каждый не входящий в D город соединён дорогой с одним из городов множества D. Известно, что в каждом доминирующем множестве хотя бы k городов. Докажите, что страну можно разбить на 2001 – k республик так, что никакие два города из одной республики не будут соединены дорогой.
На плоскости даны два таких конечных набора P1 и P2 выпуклых многоугольников, что любые два многоугольника из разных наборов имеют общую точку и в каждом из двух наборов P1 и P2 есть пара непересекающихся многоугольников. Докажите, что существует прямая, пересекающая все многоугольники обоих наборов.
На прямоугольном столе лежат равные картонные квадраты n различных цветов со сторонами, параллельными сторонам стола. Если рассмотреть любые n квадратов различных цветов, то какие-нибудь два из них можно прибить к столу одним гвоздем. Докажите, что все квадраты некоторого цвета можно прибить к столу2n-2гвоздями.