В некотором городе сеть автобусных маршрутов устроена так, что каждые два маршрута имеют ровно одну общую остановку, и на каждом маршруте есть хотя бы 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гвоздями.
Дана последовательность неотрицательных чисел a1 , a2 , an . Для любого k от 1 до n обозначим через mk величину l=1,2,..,k . Докажите, что при любом α>0число тех k , для которых mk>α , меньше, чемa1+a2+...+an α.
На координатной плоскости дан выпуклый пятиугольник ABCDE с вершинами в целых точках. Докажите, что внутри или на границе пятиугольника A1B1C1D1E1 (см. рис.) есть хотя бы одна целая точка.
В некоторой группе из 12 человек среди каждых девяти найдутся пять попарно знакомых. Докажите, что в этой группе найдутся шесть попарно знакомых.
Докажите, что три выпуклых многоугольника на плоскости нельзя пересечь одной прямой тогда и только тогда, когда каждый многоугольник можно отделить от двух других прямой (т.е. существует прямая такая, что этот многоугольник и два остальных лежат по ее разные стороны).
Часть подмножеств некоторого конечного множества выделена. Каждое выделенное подмножество состоит в точности из2k элементов ( k – фиксированное натуральное число). Известно, что в каждом подмножестве, состоящем не более чем из(k+1)2 элементов, либо не содержится ни одного выделенного подмножества, либо все в нем содержащиеся выделенные подмножества имеют общий элемент. Докажите, что все выделенные подмножества имеют общий элемент.
Даны два выпуклых многоугольника. Известно, что расстояние между любыми двумя вершинами первого не больше1, расстояние между любыми двумя вершинами второго также не больше 1, а расстояние между любыми двумя вершинами разных многоугольников больше, чем1/ . Докажите, что многоугольники не имеют общих внутренних точек.
На плоскости нарисовано некоторое семейство S правильных треугольников, получающихся друг из друга параллельными переносами, причем любые два треугольника пересекаются. Докажите, что найдутся три точки такие, что любой треугольник семейства S содержит хотя бы одну из них.
Внутри выпуклого пятиугольника выбраны две точки. Докажите, что можно выбрать четырёхугольник с вершинами в вершинах пятиугольника так, что внутрь него попадут обе выбранные точки.
На тарелке лежат 9 разных кусочков сыра. Всегда ли можно разрезать один из них на две части так, чтобы полученные 10 кусочков делились бы на две порции равной массы по 5 кусочков в каждой?
Контуры выпуклых многоугольников F и G не имеют общих точек, причём G расположен внутри F. Хорду многоугольника F – отрезок, соединяющий две точки контура F, назовём опорной для G, если она пересекается с G только по точкам контура: содержит либо только вершину, либо сторону G. а) Докажите, что найдётся опорная хорда, середина которой принадлежит контуру G. б) Докажите, что найдутся две такие хорды.
Имеется 25 кусков сыра разного веса. Всегда ли можно один из этих кусков разрезать на две части и разложить сыр в два пакета так, что части разрезанного куска окажутся в разных пакетах, веса пакетов будут одинаковы и число кусков в пакетах также будет одинаково?
На стол положили (с перекрытиями) несколько одинаковых салфеток, имеющих форму единичного круга. Всегда ли можно вбить в стол несколько точечных гвоздей так, что все салфетки будут прибиты, причём одинаковым количеством гвоздей? (Вбивать гвозди на границы кругов запрещено.)
В стране некоторые пары городов соединены односторонними прямыми авиарейсами (между любыми двумя городами есть не более одного рейса). Скажем, что город A доступен для города B, если из B можно долететь в A, возможно, с пересадками. Известно, что для любых двух городов P и Q существует город R, для которого и P, и Q доступны. Докажите, что существует город, для которого доступны все города страны. (Считается, что город доступен для себя.)