Задача 31079

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

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

Условие

Есть 20 карточек, у каждой из которых на двух сторонах написано по числу. При этом все числа от 1 до 20 написаны по два раза.
Доказать, что карточки можно разложить так, чтобы все числа сверху были различны.

Решение

Отложим карточки, на которых написано по два одинаковых числа. Возьмём одну из оставшихся карточек. Пусть на ней написаны числа a и b. Положим её числом a вверх. Далее найдём карточку, на которой написано второе число b и положим её числом b вверх. Так будем продолжать, пока не дойдём до карточки, на которой написано второе число a. На этом цикл заканчивается. Если карточки еще остались, начнём новый цикл и т.д.

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

книга
Автор	Иванов С.В.
Название	Математический кружок
глава
Номер	5
Название	Графы
Тема	Теория графов
задача
Номер	11