===== ММ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 различны.\\ 
Допустим, что в графе есть циклы и вершина x - наибольшая (в смысле сравнения натуральных чисел) в одном из циклов. Cмежные ей вершины - a-x и b-x. А этим вершинам, кроме x, смежны вершины b-a+x и a-b+x. Ясно. что одно из этих чисел больше x, что противоречит выбору x. Значит, G не имеет циклов ни при каких a и b.\\ 
Для графа, степени вершин которого не превосходят 2, и не имеющего циклов, условия пунктов a-в равносильны. Для того, чтобы каждое из них выполнялось необходимо и достаточно, чтобы в G было 2009 ребер.\\
Легко видеть. что количество a-ребер в G равно m(a)=1005 - ceil(|2011-a|/2). Ясно,что $m(a)≤ 1005$ и максимум достигается лишь при $a = 2011$. Значение 1004 досгитается при a ∈ {2009, 2010, 2012, 2013}$
Аналогичные соотношения имеют место для b-ребер.
Поэтому общее число ребер m=m(a)+m(b) может достигать 2009 только тогда, когда одно a, b равно 2011. а другое отлчается от него не более чем на 2.

**Ответ:** Граф G связен, является деревом, является цепью тогда и только тогда. когда ровно одно из чисел a, b равно 2011, другое отличется от 2011 не более чем на 2. Граф G не содержит циклов ни при каких a и b. 

**Обсуждение**

Как и в предыдущих марафонских задачах под графом я понимал классичиеский граф, в частности, не имеющий петель.
Нкоторые участники допускали наличие петель и получили несколько иные ответы. Их решения я считал верными. Самые предусмотрительные рассмотрели оба случая :) 

Получаемые при подходящих a и b цепи можно выписать явно:\\
{a, b} = {2009, 2011} - 2009-2-2007-4-2005-6-...-3-2008-1-2010;\\ 
{a, b} = {2010, 2011} - 1005-1006-1004-1007-1003-...-2008-2-2009-1-2010;\\ 
{a, b} = {2011, 2012} - 1-2010-2-2009-3-2008-...-508-504-507-505-506;\\ 
{a, b} = {2011, 2013} - 1-2010-3-1008-5-...-6-2007-4-2009-2.

Разумеется, задача легко обобщается на граф с произвольным количеством вершин n.
При четных n (больших 2) для выполнения условий пунктов а-в одно из чисел a, b должно быть равно n+1, а другое отличаться от первого не более, чем на 2. 
При нечетных n (больших 1) - a и b должны быть, двумя элементами множества {n, n+1, n+2}.

**Награды**

За правильное решение задачи Сергей Половинкин, Владислав Франк, Алексей Волошин. Евгений Гужавин, Анатолий Казмерчук и Дмитрий Пашуткин получают по 3 призовых балла, а Александр Ларин - 2 призовых балла.

**Эстетическая оценка задачи 4.4 балла**
----

//Разбор задачи ММ131 подготовил Владимир Лецко//

----