В стране есть N городов. Некоторые пары из них соединены беспосадочными двусторонними авиалиниями. Оказалось, что для любого k (2 ≤ k ≤ N) при любом выборе k городов количество авиалиний между этими городами не будет превосходить 2k – 2. Докажите, что все авиалинии можно распределить между двумя авиакомпаниями так, что не будет замкнутого авиамаршрута, в котором все авиалинии принадлежат одной компании.
При каком наименьшем для любого набора из множеств найдется такой набор из множеств, что каждое множество набора является пересечением двух различных множеств набора ?
На столе лежат купюры достоинством 1, 2, .. ,2n тугриков. Двое ходят по очереди. Каждым ходом игрок снимает со стола две купюры, большую отдает сопернику, а меньшую забирает себе. Каждый стремится получить как можно больше денег. Сколько тугриков получит начинающий при правильной игре?
В круговых автогонках участвовали четыре гонщика. Их машины стартовали одновременно из одной точки и двигались с постоянными скоростями. Известно, что после начала гонок для каждых трёх машин нашёлся момент, когда они встретились. Докажите, что после начала гонок найдётся момент, когда встретятся все четыре машины. (Гонки считаем бесконечно долгими по времени.)
а) В 99 ящиках лежат яблоки и апельсины. Докажите, что можно так выбрать 50 ящиков, что в них окажется не менее половины всех яблок и не менее половины всех апельсинов. б) В 100 ящиках лежат яблоки и апельсины. Докажите, что можно так выбрать 34 ящика, что в них окажется не менее трети всех яблок и не менее трети всех апельсинов.
Даны N≥ 3 точек, занумерованных числами 1, 2, ...,N. Каждые две точки соединены стрелкой от меньшего номера к большему. Раскраску всех стрелок в красный и синий цвета назовемоднотонной, если нет двух таких точекAиB, что отAдоBможно добраться и по красным стрелкам, и по синим. Найдите количество однотонных раскрасок.
В 100 ящиках лежат яблоки, апельсины и бананы. Докажите, что можно так выбрать 51 ящик, что в них окажется не менее половины всех яблок, не менее половины всех апельсинов и не менее половины всех бананов.
Каждая клетка клетчатой плоскости раскрашена в один изn² цветов так, что в каждом квадрате изn×клеток встречаются все цвета. Известно, что в какой-то строке встречаются все цвета. Докажите, что существует столбец, раскрашенный ровно вnцветов.
Докажите, что в любом множестве, состоящем из 117 попарно различных трёхзначных чисел, можно выбрать четыре попарно непересекающихся подмножества, суммы чисел в которых равны.
В прямоугольной таблице 9 строк и 2004 столбца. В её клетках расставлены числа от 1 до 2004, каждое – по 9 раз. При этом в каждом столбце числа различаются не более чем на 3. Найдите минимальную возможную сумму чисел в первой строке.
По периметру круглого торта диаметром n/p метров расположены n вишенок. Если на концах некоторой дуги находятся вишенки, то количество остальных вишенок на этой дуге меньше, чем длина дуги в метрах. Докажите, что торт можно разрезать на n равных секторов так, что в каждом куске будет по вишенке.
Решите в натуральных числах уравнение (1 + nk)l = 1 + nm, где l > 1.
Прямая пересекает отрезок в точке . Какое максимальное число точек может найтись на этой прямой так, чтобы один из углов и был в два раза больше другого?
Биссектриса угла треугольника () пересекает описанную окружность в точке . Перпендикуляр к в точке пересекает биссектрису угла в точке . Окружность с центром в точке и радиусом пересекает меньшую дугу описанной окружности в точке . Докажите, что в четырехугольник можно вписать окружность.