Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание

ММ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 подготовил Владимир Лецко


 

 


Страница: [[marathon:problem_131]]

marathon/problem_131.txt · Последние изменения: 2011/06/13 21:28 (внешнее изменение)
Powered by DokuWiki  ·  УКЦ ВГПУ 2006