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

Задачи

Страница: << 24 25 26 27 28 29 30 >> [Всего задач: 383]

Задача 111793

Темы:	[	Ориентированные графы	]
	[	Разбиения на пары и группы; биекции	]
	[	Доказательство от противного	]

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

Автор: Гарбер М.

В классе учится 15 мальчиков и 15 девочек. В день 8 Марта некоторые мальчики позвонили некоторым девочкам и поздравили их с праздником (никакой мальчик не звонил одной и той же девочке дважды). Оказалось, что детей можно единственным образом разбить на 15 пар так, чтобы в каждой паре оказались мальчик с девочкой, которой он звонил. Какое наибольшее число звонков могло быть сделано?

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

Решение

Задача 30793

Тема:

[

Деревья

]

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

Докажите, что в любом связном графе можно удалить вершину вместе со всеми выходящими из нее рёбрами так, чтобы он остался связным.

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

Решение

Задача 30794

Темы:	[	Деревья	]
	[	Принцип крайнего (прочее)	]
	[	Индукция (прочее)	]

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

В стране 100 городов, некоторые из которых соединены авиалиниями. Известно, что от каждого города можно долететь до любого другого (возможно, с пересадками). Докажите, что можно побывать во всех городах, совершив не более а) 198 перёлетов; б) 196 перелётов.

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

Решение

Задача 30803

Тема:

[

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

]

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

Докажите, что в плоском графе есть вершина, степень которой не превосходит 5.

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

Решение

Задача 30804

Темы:	[	Планарные графы. Формула Эйлера	]
Темы:	[	Сочетания и размещения	]

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

Каждое ребро полного графа с 11 вершинами покрашено в один из двух цветов: красный или синий.
Докажите, что либо "красный", либо "синий" граф не является плоским.

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

Решение

Страница: << 24 25 26 27 28 29 30 >> [Всего задач: 383]