Задача
Даны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, останутся карточки, то мы можем повторить для них ту же самую процедуру.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь