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

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

Условие

Даны n карточек; на обеих сторонах каждой карточки написано по одному из чисел 1, 2,..., n, причём так, что каждое число встречается на всех n карточках ровно два раза. Доказать, что карточки можно разложить на столе так, что сверху окажутся все числа: 1, 2,..., n.

Решение

Возьмём произвольную карточку. На ней написаны числа a1 и a2. Положим её числом a1 вверх. Если a2$ \ne$a1, то найдётся карточка с числами a2 и a3. Положим её числом a2 вверх. Ясно, что a3$ \ne$a2, поскольку иначе одно число встречалось бы по крайней мере три раза. Если a3$ \ne$a1, то найдётся карточка с числами a3 и a4; положим её числом a3 вверх. Ясно, что a4 отлично от a2 и a3. Если a4$ \ne$a1, то найдётся карточка с числами a4 и a5 и т.д. Если после того как мы выложим карточку с числами an и a1, останутся карточки, то мы можем повторить для них ту же самую процедуру.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 25
Год 1962
вариант
1
Класс 7
Тур 1
задача
Номер 5
олимпиада
Название Московская математическая олимпиада
год
Номер 25
Год 1962
вариант
1
Класс 8
Тур 1
задача
Номер 5
олимпиада
Название Московская математическая олимпиада
год
Номер 25
Год 1962
вариант
1
Класс 10
Тур 1
задача
Номер 5

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

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