ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Все авторы >> Райгородский А. М.

Фильтр
Сложность с по   Класс с по  
Все задачи автора

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



Задача 65676

Темы:   [ Правило произведения ]
[ Теория графов (прочее) ]
Сложность: 4+
Классы: 8,9,10

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

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

Задача 115509

Темы:   [ Теория графов (прочее) ]
[ Принцип крайнего (прочее) ]
[ Перестройки ]
[ Доказательство от противного ]
[ Правильный (равносторонний) треугольник ]
Сложность: 5+
Классы: 9,10,11

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

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

Задача 116695

Темы:   [ Теория графов (прочее) ]
[ Сочетания и размещения ]
[ Принцип Дирихле ]
[ Объединение, пересечение и разность множеств ]
[ Примеры и контрпримеры. Конструкции ]
Сложность: 5+
Классы: 10

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

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

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



© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .