Задача 77930

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

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

Условие

На консультации было 20 школьников и разбиралось 20 задач. Оказалось, что каждый из школьников решил две задачи и каждую задачу решили два школьника. Докажите, что можно так организовать разбор задач, чтобы каждый школьник рассказал одну из решённых им задач и все задачи были разобраны.

Решение 1

Дадим каждому школьнику карточку, на которой он напишет номера решённых им задач. Теперь задача свелась к задаче 31079.

Решение 2

Рассмотрим граф, вершинами которого являются школьники и задачи, а рёбра соединяют каждого школьника с решёнными им задачами. Степень каждой вершины равна 2, следовательно, граф распадается на циклы. Обходя по циклу в каком-то направлении, мы за каждым школьником получаем номер рассказываемой им задачи.

Источники и прецеденты использования

книга
Автор	Иванов С.В.
Название	Математический кружок
глава
Номер	5
Название	Графы
Тема	Теория графов
задача
Номер	05
олимпиада
Название	Турнир им.Ломоносова
год/номер
Номер	12
Дата	1989
задача
Номер	05
олимпиада
Название	Московская математическая олимпиада
год
Номер	14
Год	1951
вариант
Класс	7,8
Тур	2
задача
Номер	3