Каталог по темам

Задачи

Страница: << 7 8 9 10 11 12 13 >> [Всего задач: 85]

Задача 116695

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

Сложность: 5+
Классы: 10

Автор: Райгородский А. М.

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

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

Решение

Задача 67496

Темы:	[	Теория графов (прочее)	]
	[	Процессы и операции	]
	[	Кооперативные алгоритмы	]
	[	Индукция (прочее)	]

Сложность: 5+
Классы: 9,10,11

Автор: Васильев Т.

Замок Мерлина состоит из 100 комнат и 1000 коридоров. Каждый коридор соединяет какие-то две комнаты, каждые две комнаты соединены не более чем одним коридором. Мерлин выдал мудрецам план замка и объявил испытание. Мудрецы должны будут распределиться по комнатам, как хотят. Далее каждую минуту Мерлин указывает коридор, и один из мудрецов переходит по нему из комнаты на любом его конце в комнату на другом его конце. Мерлин победит, если когда-то укажет коридор, на концах которого нет мудрецов.
Число $m$ назовём волшебным числом замка, если $m$ мудрецов могут, сговорившись перед испытанием, действовать так, чтобы никогда не проиграть, причём $m$ — минимальное такое число. Чему может равняться волшебное число замка? (Все, включая Мерлина, всегда знают расположение всех мудрецов.)

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

Задача 34862

Темы:	[	Сочетания и размещения	]
Темы:	[	Теория графов (прочее)	]

Сложность: 2+
Классы: 8,9,10

В парламенте 30 депутатов. Каждые два из них либо дружат, либо враждуют, причём каждый дружит ровно с шестью другими. Каждые три депутата образуют комиссию. Найдите общее число комиссий, в которых все три члена попарно дружат или все трое попарно враждуют.

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

Решение

Задача 21995

Темы:	[	Принцип Дирихле (прочее)	]
Темы:	[	Теория графов (прочее)	]

Сложность: 3
Классы: 6,7,8

Докажите, что среди любых шести человек есть либо трое попарно знакомых, либо трое попарно незнакомых.

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

Решение

Задача 97897

Темы:	[	Турниры и турнирные таблицы	]
	[	Теория графов (прочее)	]
	[	Четность и нечетность	]

Сложность: 3
Классы: 8,9,10

Автор: Генкин С.А.

20 футбольных команд проводят первенство. В первый день все команды сыграли по одной игре. Во второй также все команды сыграли по одной игре.
Докажите, что после второго дня можно указать такие 10 команд, что никакие две из них не играли друг с другом.

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

Решение

Страница: << 7 8 9 10 11 12 13 >> [Всего задач: 85]