|
||||||||||||||||||
|
СодержаниеММ131Конкурсная задача ММ131 (3 балла) (Прощай 2010-й)
Граф G=<V,E> задан на множестве V = {1, 2, …, 2010} по правилу: {x,y} ∈ E ⇔ x+y = a или x+y = b, где a и b - фиксированные натуральные числа.
При каких a и b, граф G: Решение
Ребро {x,y} такое, что x+y = a будем называть a-ребром, иначе b-ребром.
Ясно, что степень каждой вершины не больше 2, поскольку ей инцидентны не более одного ребра каждого типа.
При a = b степени вершин G не больше 1. Такие графы не могу удовлетворять условиям пунктов а-г. Поэтому можно считать, a и b различны. Ответ: Граф G связен, является деревом, является цепью тогда и только тогда. когда ровно одно из чисел a, b равно 2011, другое отличется от 2011 не более чем на 2. Граф G не содержит циклов ни при каких a и b. Обсуждение Как и в предыдущих марафонских задачах под графом я понимал классичиеский граф, в частности, не имеющий петель. Нкоторые участники допускали наличие петель и получили несколько иные ответы. Их решения я считал верными. Самые предусмотрительные рассмотрели оба случая :)
Получаемые при подходящих a и b цепи можно выписать явно: Разумеется, задача легко обобщается на граф с произвольным количеством вершин n. При четных n (больших 2) для выполнения условий пунктов а-в одно из чисел a, b должно быть равно n+1, а другое отличаться от первого не более, чем на 2. При нечетных n (больших 1) - a и b должны быть, двумя элементами множества {n, n+1, n+2}. Награды За правильное решение задачи Сергей Половинкин, Владислав Франк, Алексей Волошин. Евгений Гужавин, Анатолий Казмерчук и Дмитрий Пашуткин получают по 3 призовых балла, а Александр Ларин - 2 призовых балла. Эстетическая оценка задачи 4.4 балла Разбор задачи ММ131 подготовил Владимир Лецко
|
|||||||||||||||||
|
||||||||||||||||||
|