===== ММ132 =====

**Конкурсная задача ММ132 ** (5 баллов) (Здравствуй 2011-й)

Граф G=<V,E> задан на множестве V = {1, 2,..., 2011} по правилу: {x,y} ∈ E <=> |x-y| > a , где a - фиксированное натуральное число, меньшее 1006.\\
Сколько периферийных вершин может иметь граф G?

Примечание: Вершина графа называется периферийной, если ее эксцентриситет равен диаметру графа.

**Решение** 

Рассмотрим три случая.

1. а=1005.\\
В этом случае граф не связен и, следовательно, не имеет периферийных вершин.

2. 670 ≤ a ≤ 1005.\\
В этом случае диаметр графа равен 3.\\
Вершины эксцентриситета 3 будут сосредоточены на двух промежутках [2011-2a,..., a+1] и [2011-a, ..., 2a+1].
Например, кратчайший путь из вершины 2011-2a в вершину 2011-a будет таким: 2011-2a -> 2011 -> 1 -> 2011-a.\\
В то же время: \\
от вершин из промежутка [1, ..., 2011-2a] до любой вершины можно добраться либо за один шаг, либо через вершину 2011;\\
аналогично не более чем за два шага можно добраться до любой вершины от вершин из промежутка [2a+2, ..., 2011].\\
Наконец, от вершин из промежутка [a+2, ..., 2010-a] можно добраться не более чем за два шага до любой вершины (через вершину 1 до вершин с бОльшими номерами и через вершину 2011 до вершин с меньшими номерами).\\
Таким образом, количество периферийный вершин равно (a+2-(2011-2a))+(2a+2-(2011-a))=6a-4018.\\
При значениях a из рассматриваемого диапазона это дает нам следующий набор допустимых количеств периферийных вершин: 2,8,14,..., 2006.

3. a<670\\
В этом случае каждая вершина имеет эксцентриситет 2. Поэтому все 2011 вершин будут периферийными.

**Ответ:**: 2, 8, 14, 20..., 2000, 2006, 2011 (или ни одной).  


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

К моему удивлению, серьезные разногласия и путаницу вызвал случай a=1005.\\
Полагаю, кроме варианта, приведенного в решении, имеет право на существование и такой: поскольку граф не связен, эксцентриситет каждой вершины бесконечен и все вершины являются периферийными.\\
Каким образом некоторые участники смогли насчитать 2008, 2010 или и вовсе одну периферийную вершину -  для меня загадка.

Марафонцы существенно разошлись во мнениях, давая эстетическую оценку задаче ММ132. Для меня задачка любопытна немного неожиданным расположением периферийных вершин в G с точки зрения обычной упорядоченности вершин: и не по краям, и не в серединке. 
 

**Награды**

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


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


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