Страница: 1 [Всего задач: 3]      

В стране лингвистов существует n языков. Там живет m людей, каждый из которых знает ровно три языка, причём для разных людей эти наборы различны. Известно, что максимальное число людей, любые два из которых могут поговорить без посредников, равно k. Оказалось, что  11n ≤ k ≤ ^m/₂.
Докажите, что тогда в стране найдутся хотя бы mn пар людей, которые не смогут поговорить без посредников.

Прислать комментарий

Решение

На плоскости отметили 4n точек, после чего соединили отрезками все пары точек, расстояние между которыми равно 1 см. Оказалось, что среди любых  n + 1  точек обязательно есть две, соединённые отрезком. Докажите, что всего проведено не менее 7n отрезков.

Прислать комментарий

Решение

Рассмотрим граф, у которого вершины соответствуют всевозможным трёхэлементным подмножествам множества  {1, 2, 3, ..., 2^k},  а рёбра проводятся между вершинами, которые соответствуют подмножествам, пересекающимся ровно по одному элементу. Найдите минимальное количество цветов, в которые можно раскрасить вершины графа так, чтобы любые две вершины, соединённые ребром, были разного цвета.

Прислать комментарий

Решение

Страница: 1 [Всего задач: 3]