Условие
Даны
n карточек; на обеих сторонах каждой карточки написано по одному из
чисел
1, 2,...,
n, причём так, что каждое число встречается на всех
n
карточках ровно два раза. Доказать, что карточки можно разложить на столе так,
что сверху окажутся все числа:
1, 2,...,
n.
Решение
Возьмём произвольную карточку. На ней написаны числа
a1 и
a2. Положим
её числом
a1 вверх. Если
a2
a1, то найдётся карточка с числами
a2 и
a3. Положим её числом
a2 вверх. Ясно, что
a3a2,
поскольку иначе одно число встречалось бы по крайней мере три раза. Если
a3a1, то найдётся карточка с числами
a3 и
a4; положим её числом
a3 вверх. Ясно, что
a4 отлично от
a2 и
a3. Если
a4a1, то
найдётся карточка с числами
a4 и
a5 и т.д. Если после того как мы
выложим карточку с числами
an и
a1, останутся карточки, то мы можем
повторить для них ту же самую процедуру.
Источники и прецеденты использования
