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

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

Условие

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


Решение

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

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

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

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

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