Выбрано 14 задач 
Убрать все задачи
На книжной полке стоят 30 томов энциклопедии в некотором порядке. За одну операцию разрешается менять местами любые два соседних тома. За какое наименьшее число операций можно гарантированно выстроить все тома в правильном порядке (с первого по тридцатый слева направо) независимо от начального положения?
Жили-были двадцать шпионов. Каждый из них написал донос на десять своих коллег.
Докажите, что не менее, чем десять пар шпионов донесли друг на друга.
В прямоугольном треугольнике ABC (∠B = 90°) проведена высота BH. Окружность, вписанная в треугольник ABH, касается сторон AB, AH в точках H1, B1 соответственно; окружность, вписанная в треугольник CBH, касается сторон CB, CH в точках H2, B2 соответственно. Пусть O – центр описанной окружности треугольника H1BH2. Докажите, что OB1 = OB2.
В ориентированном графе 101 вершина. У каждой вершины число входящих и число выходящих рёбер равно 40.
Доказать, что из каждой вершины можно попасть в любую другую, пройдя не более чем по трём ребрам.
В стране есть n > 1 городов, некоторые пары городов соединены двусторонними беспосадочными авиарейсами. При этом между каждыми двумя городами существует единственный авиамаршрут (возможно, с пересадками). Мэр каждого города X подсчитал количество таких нумераций всех городов числами от 1 до n, что на любом авиамаршруте, начинающемся в X, номера городов идут в порядке возрастания. Все мэры, кроме одного, заметили, что их результаты подсчётов делятся на 2016. Докажите, что и у оставшегося мэра результат также делится на 2016.
В выпуклом четырехугольнике $ABCD$ точки $K$, $L$, $M$, $N$ – середины сторон $BC$, $CD$, $DA$, $AB$ соответственно. Отрезки $AK$, $BL$, $CM$, $DN$, пересекаясь, делят друг друга на три части. Оказалось, что отношение длины средней части к длине всего отрезка одно и то же для всех четырех отрезков. Верно ли, что $ABCD$ – параллелограмм?
Средняя линия трапеции равна 10 и делит площадь трапеции в отношении 3:5. Найдите основания трапеции.
Диагонали четырехугольника ABCD пересекаются
в точке P, причем
SABP2 + SCDP2 = SBCP2 + SADP2.
Докажите, что P — середина одной из диагоналей.
Сколько существует шестизначных чисел, у которых по три чётных и нечётных цифры?
Школьник едет на кружок на трамвае, платит рубль и получает сдачу. Доказать, что если он обратно также поедет в трамвае, то он сможет уплатить за проезд без сдачи. (Примечание. Проезд в трамвае стоил 30 коп. В обращении находились монеты достоинством в 1, 2, 3, 5, 10, 15 и 20 коп.)
Сколькими способами можно переставить буквы слова "ЭПИГРАФ" так, чтобы и гласные, и согласные шли в алфавитном порядке?
На листе бумаги отмечены точки A, B, C, D. Распознающее устройство может абсолютно точно выполнять два типа операций: а) измерять в сантиметрах расстояние между двумя заданными точками; б) сравнивать два заданных числа. Какое наименьшее число операций нужно выполнить этому устройству, чтобы наверняка определить, является ли четырёхугольник ABCD прямоугольником?
Имеется система уравнений
*x + *y + *z = 0,*x + *y + *z = 0,
*x + *y + *z = 0.
Два человека поочерёдно вписывают вместо звёздочек числа.
Доказать, что начинающий всегда может добиться того, чтобы система имела ненулевое решение.
Пусть n и b – натуральные числа. Через V(n, b) обозначим число разложений n на сомножители, каждый из которых больше b (например:
36 = 6·6 = 4·9 = 3·3·4 = 3·12, так что V(36, 2) = 5). Докажите, что V(n, b) < n/b.
|
|
 |
Условие
Пусть n и b – натуральные числа. Через V(n, b) обозначим число разложений n на сомножители, каждый из которых больше b (например:
36 = 6·6 = 4·9 = 3·3·4 = 3·12, так что V(36, 2) = 5). Докажите, что V(n, b) < n/b.
Решение
Индукция по n. База (n = 1) очевидна: V(1, b) = 0.
Шаг индукции. Предположим теперь, что это неравенство верно при всех m < n.
Для каждого делителя k > b числа n рассмотрим все разложения числа n, в которых минимальный сомножитель равен k. Количество таких разложений равно V(n/k, k – 1). Исключение составляет случай k = n – такое разложение одно, а V(n/n, n – 1) = 0. Следовательно,
Замечания
12 баллов
