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

Задачи

Страница: << 57 58 59 60 61 62 63 >> [Всего задач: 383]

Задача 109769

Темы:	[	Степень вершины	]
	[	Связность и разложение на связные компоненты	]
	[	Правило произведения	]

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

Автор: Лифшиц Ю.

Гидры состоят из голов и шей (каждая шея соединяет ровно две головы). Одним ударом меча можно снести все шеи, выходящие из какой-то головы A гидры. Но при этом из головы A мгновенно вырастает по одной шее во все головы, с которыми A не была соединена. Геракл побеждает гидру, если ему удастся разрубить её на две несвязанные шеями части. Найдите наименьшее N, при котором Геракл сможет победить любую стошеюю гидру, нанеся не более чем N ударов.

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

Решение

Задача 109805

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

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

Авторы: Карпов Д.В., Смирнов А.

В стране 1001 город, каждые два города соединены дорогой с односторонним движением. Из каждого города выходит ровно 500 дорог, в каждый город входит ровно 500 дорог. От страны отделилась независимая республика, в которую вошли 668 городов. Докажите, что из каждого города этой республики можно доехать до любого другого ее города, не выезжая за пределы республики.

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

Решение

Задача 111833

Темы:	[	Связность и разложение на связные компоненты	]
	[	Степень вершины	]
	[	Перестройки	]
	[	Принцип крайнего (прочее)	]

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

Авторы: Богданов И.И., Челноков Г.Р.

В стране есть N городов. Некоторые пары из них соединены беспосадочными двусторонними авиалиниями. Оказалось, что для любого k (2 ≤ k ≤ N) при любом выборе k городов количество авиалиний между этими городами не будет превосходить 2k – 2. Докажите, что все авиалинии можно распределить между двумя авиакомпаниями так, что не будет замкнутого авиамаршрута, в котором все авиалинии принадлежат одной компании.

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

Решение

Задача 116645

Темы:	[	Разрезания на части, обладающие специальными свойствами	]
	[	Степень вершины	]
	[	Комбинаторная геометрия (прочее)	]

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

Авторы: Богданов И.И., Подлипский О.К.

Клетчатый квадрат 2010×2010 разрезан на трёхклеточные уголки. Докажите, что можно в каждом уголке отметить по клетке так, чтобы в каждой вертикали и в каждой горизонтали было поровну отмеченных клеток.

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

Решение

Задача 98331

Темы:	[	Четность перестановки	]
	[	Обход графов	]
	[	Перестройки	]

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

Автор: Фомин С.В.

а) Четыре порта 1, 2, 3, 4 расположены (в этом порядке) на окружности круглого острова. Их связывает плоская сеть дорог, на которых могут быть перекрёстки, то есть точки, где пересекаются, сходятся или разветвляются дороги. На всех участках дорог введено одностороннее движение так, что, выехав от любого порта или перекрёстка, нельзя вернуться в него снова. Пусть f_ij означает число различных путей, идущих из порта i в порт j. Докажите неравенство f₁₄f₂₃ ≥ f₁₃f₂₄.
б) Докажите, что если портов шесть: 1, 2, 3, 4, 5, 6 (по кругу в этом порядке), то f₁₆f₂₅f₃₄ + f₁₅f₂₄f₃₆ + f₁₄f₂₆f₃₅ ≥ f₁₆f₂₄f₃₅ + f₁₅f₂₆f₃₄ + f₁₄f₂₅f₃₆.

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

Решение

Страница: << 57 58 59 60 61 62 63 >> [Всего задач: 383]