ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 77930
Темы:    [ Степень вершины ]
[ Обход графов ]
[ Процессы и операции ]
Сложность: 3
Классы: 8,9
В корзину
Прислать комментарий

Условие

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


Решение 1

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


Решение 2

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

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

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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .