Выбрано 25 задач 
Убрать все задачи
За круглым столом сидят 30 человек – рыцари и лжецы (рыцари всегда говорят правду, а лжецы всегда лгут). Известно, что у каждого из них за этим же столом есть ровно один друг, причём у рыцаря этот друг – лжец, а у лжеца этот друг – рыцарь (дружба всегда взаимна). На вопрос "Сидит ли рядом с вами ваш друг?" сидевшие через одного ответили "Да". Сколько из остальных могли также ответить "Да"?
Даны различные натуральные числа a1, a2, ..., a14. На доску выписаны все 196 чисел вида ak + al, где 1 ≤ k, l ≤ 14. Может ли оказаться, что для каждой комбинации из двух цифр среди написанных на доске чисел найдётся хотя бы одно число, оканчивающееся на эту комбинацию (то есть найдутся числа, оканчивающиеся на 00, 01, 02, ..., 99)?
Рассматриваются девятизначные числа, состоящие из неповторяющихся цифр от
1 до 9 в разном порядке. Пара таких чисел называется кондиционной, если их
сумма равна 987654321.
а) Доказать, что найдутся хотя бы две кондиционные пары ((a, b) и (b, a) – одна и та же пара).
б) Доказать, что кондиционных пар – нечётное число.
Дано:
Докажите, что
На диаметре AC некоторой окружности дана точка E. Проведите через неё хорду BD так, чтобы площадь четырёхугольника ABCD была наибольшей.
Числа 21989 и 51989 выписали одно за другим (в десятичной записи). Сколько всего цифр выписано?
Десятичная запись натурального числа a состоит из n цифр, а десятичная запись числа a³ состоит из m цифр. Может ли m + n равняться 2001?
Шесть игральных костей нанизали на спицу так, что каждая может вращаться независимо от остальных (протыкаем через центры противоположных граней). Спицу положили на стол и прочитали число, образованное цифрами на верхних гранях костей. Докажите, что можно так повернуть кости, чтобы это число делилось на 7. (На гранях стоят цифры от 1 до 6, сумма цифр на противоположных гранях равна 7.)
Окружность S1 касается сторон угла ABC в точках A и C. Окружность S2 касается прямой AC в точке C и проходит через точку B. Окружность S1 она пересекает в точке M. Докажите, что прямая AM делит отрезок BC пополам.
Петя разрезал прямоугольный лист бумаги по прямой. Затем он разрезал по прямой один из получившихся кусков. Затем он проделал то же самое с одним из трёх получившихся кусков и т.д. Докажите, что после достаточного количества разрезаний можно будет выбрать среди получившихся кусков 100 многоугольников с одинаковым числом вершин (например, 100 треугольников или 100 четырёхугольников и т.д.).
В трапеции ABCD известно, что AB=BC=CD . Диагонали трапеции пересекаются в точке O . Окружность, описанная около треугольника ABO , пересекает основание AD в точке E . Докажите, что BEDC — ромб.
В основании A1A2...An
пирамиды SA1A2...An лежит точка O, причём SA1 = SA2 = ... = SAn и ∠SA1O = ∠SA2O = ... = ∠SAnO.
При каком наименьшем значении n отсюда следует, что SO – высота пирамиды?
Расшифровать пример на умножение, если буквой Ч зашифрованы чётные числа, а буквой Н – нечётные.
В ящиках лежат орехи. Известно, что в среднем в каждом ящике 10 орехов, а среднее арифметическое квадратов чисел орехов в ящиках меньше 1000. Докажите, что по крайней мере 10% ящиков не пустые.
Из вершин произвольного выпуклого четырёхугольника опущены перпендикуляры на его диагонали.
Докажите, что четырёхугольник, вершинами которого являются основания этих перпендикуляров, подобен исходному.
Найдётся ли среди чисел вида 1...1 число, которое делится на 57?
По шоссе в одну сторону движутся пешеход и велосипедист, в другую сторону – телега и машина. Все участники движутся с постоянными скоростями (каждый со своей). Велосипедист сначала обогнал пешехода, потом через некоторое время встретил телегу, а потом ещё через такое же время встретил машину. Машина сначала встретила велосипедиста, потом через некоторое время встретила пешехода, и потом ещё через такое же время обогнала телегу. Велосипедист обогнал пешехода в 10 часов, а пешеход встретил машину в 11 часов. Когда пешеход встретил телегу?
Пусть AA1, BB1, CC1 – высоты остроугольного треугольника ABC, OA, OB, OC – центры вписанных окружностей треугольников AB1C1, BC1A1, CA1B1 соответственно; TA, TB, TC – точки касания вписанной окружности треугольника ABC со сторонами BC, CA, AB соответственно. Докажите, что все стороны шестиугольника TAOCTBOATCOB равны.
Хозяйка сделала расстегай и хочет заранее разрезать его на такие (не обязательно равные) части, чтобы пирог можно было разделить поровну и на пятерых, и на семерых. Каким минимальным числом кусков она сможет обойтись?
На доске можно либо написать две единицы, либо стереть любые два уже написанных одинаковых числа n и написать вместо них числа n + 1 и n – 1. Какое минимальное количество таких операций требуется, чтобы получить число 2005? (Сначала доска была чистой.)
Периоды двух последовательностей – 7 и 13. Какова максимальная длина начального куска, который может у них совпадать?
Вадик написал название своего родного города и все его циклические сдвиги (перестановки по кругу), получив таблицу 1. Затем, упорядочив эти ''слова'' по алфавиту, он составил таблицу 2 и выписал её последний столбец: ВКСАМО.
Саша сделал то же самое с названием своего родного города и получил ''слово'' МТТЛАРАЕКИС. Что это за город, если его название начинается с буквы С?
Отмечены вершины и середины сторон правильного десятиугольника (то есть всего отмечено 20 точек).
Сколько существует треугольников с вершинами в отмеченных точках?
На отрезке [a, b] отмечено несколько синих и красных точек. Две точки одного цвета, между которыми нет отмеченных точек, разрешается стереть. Разрешается также отметить две точки одного цвета, красные или синие, так, чтобы между ними не было других отмеченных точек. Первоначально было отмечено две точки: a – синяя и b – красная. Можно ли сделать несколько разрешенных пребразований так, чтобы в результате было опять две отмеченные точки: a – красная и b – синяя?
В стране 100 городов и несколько дорог. Каждая дорога соединяет два каких-то города, дороги не пересекаются. Из каждого города можно добраться до любого другого, двигаясь по дорогам. Докажите, что можно объявить несколько дорог главными так, чтобы из каждого города выходило нечётное число главных дорог.
|
|
 |
Условие
В стране 100 городов и несколько дорог. Каждая дорога соединяет два каких-то города, дороги не пересекаются. Из каждого города можно добраться до любого другого, двигаясь по дорогам. Докажите, что можно объявить несколько дорог главными так, чтобы из каждого города выходило нечётное число главных дорог.
Решение 1
Разобьём все города на пары и соединим каждую пару своим маршрутом. Посчитаем для каждой дороги кратность: число маршрутов, в которые она вошла. Сумма кратностей для выходящих из города дорог нечётна: "свой" маршрут даёт вклад 1, а остальные – 0 или 2. Значит, из каждого города выходит нечётное число дорог нечётной кратности. Их и объявим главными.
Решение 2
Рассмотрим граф городов и дорог и докажем по индукции, что факт верен для любого связного графа с чётным числом вершин.
База. При n = 1 утверждение очевидно.
Шаг индукции. Пусть утверждение доказано для всех графов с меньших чем 2n (чётным) числом вершин. Возьмём связный граф на 2n вершинах и выделим в нём остовное дерево. В этом дереве возьмём любую висячую вершину А и рассмотрим вершину B, к которой она прикреплена. Если к вершине B прикреплено нечётное число висячих вершин, объявим главными все рёбра, ведущие из B в висячие вершины, удалим B и эти висячие вершины вместе со всеми выходящими из них рёбрами и применим предположение индукции к оставшемуся графу. В противном случае применим предположение индукции к графу, который получается удалением всех висячих вершин, прикреплённых к B, а потом дополнительно объявим главными все рёбра, ведущие из B в висячие вершины.
Замечания
1. См. также задачу М2232 из Задачника "Кванта" ("Квант", 2011, №4).
2. 5 баллов.
