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

Задачи

Страница: << 30 31 32 33 34 35 36 >> [Всего задач: 383]

Задача 116699

Темы:	[	Степень вершины	]
	[	Сочетания и размещения	]
	[	Мощность множества. Взаимно-однозначные отображения	]
	[	Примеры и контрпримеры. Конструкции	]

Сложность: 4
Классы: 11

Автор: Сергеев П.В.

На собрание пришло n человек (n > 1). Оказалось, что у каждых двух из них среди собравшихся есть ровно двое общих знакомых.
а) Докажите, что каждый из них знаком с одинаковым числом людей на этом собрании.
б) Покажите, что n может быть больше 4.

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

Решение

Задача 30805

Тема:

[

Планарные графы. Формула Эйлера

]

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

Семиугольник разбит на выпуклые пяти- и шестиугольники, причём так, что каждая его вершина является вершиной по крайней мере двух многоугольников разбиения. Докажите, что число пятиугольников разбиения не меньше 13.

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

Решение

Задача 64639

Темы:	[	Обход графов	]
Темы:	[	Примеры и контрпримеры. Конструкции	]

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

Автор: Жуков Г.

Можно ли n раз рассадить 2n + 1 человек за круглым столом, чтобы никакие двое не сидели рядом более одного раза, если
а) n = 5; б) n = 4; в) n – произвольное натуральное число?

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

Решение

Задача 64663

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

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

Авторы: Пахарев А., Скопенков М.Б., Устинов А.В.

Каждому городу в некоторой стране присвоен индивидуальный номер. Имеется список, в котором для каждой пары номеров указано, соединены города с данными номерами железной дорогой или нет. Оказалось, что, какие ни взять два номера M и N из списка, можно так перенумеровать города, что город с номером M получит номер N, но список по-прежнему будет верным. Верно ли, что, какие ни взять два номера M и N из списка, можно так перенумеровать города, что город с номером M получит номер N, город с номером N получит номер M, но список по-прежнему будет верным?

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

Решение

Задача 64727

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

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

Авторы: Пахарев А., Скопенков М.Б., Устинов А.В.

В королевстве некоторые пары городов соединены железной дорогой. У короля есть полный список, в котором поименно перечислены все такие пары (каждый город имеет свое собственное имя). Оказалось, что для любой упорядоченной пары городов принц может переименовать все города так, чтобы первый город оказался названным именем второго города, а король не заметил бы изменений. Верно ли, что для любой пары городов принц может переименовать все города так, чтобы первый город оказался названным именем второго города, второй город оказался названным именем первого города, а король не заметил бы изменений?

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

Решение

Страница: << 30 31 32 33 34 35 36 >> [Всего задач: 383]