Решение задачи MM131 IV открытой интернет-олимпиады по математике: XIV тура Математического марафона

главная страница сайта Приглашение в мир математики
====================================

ММ131 (3 балла) (Прощай 2010-й)

Граф $G=\left<V,E\right>$ задан на множестве $V = \{1, 2,\dots, 2010\}$ по правилу: $\{x,y\} \in E \Leftrightarrow x+y = a \vee 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-\left\lceil \frac{|2011-a|}{2}\right\rceil$. Ясно,что $m(a)\le 1005$ и максимум достигается лишь при $a = 2011$. Значение 1004 досгитается при $$a\in \{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 подготовил Владимир Лецко

Задайте вопрос на блоге о математике