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

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

ММ132 (5 баллов) (Здравствуй 2011-й)

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

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

====================================

Решение

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

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

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

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

Ответ:: $2, 8, 14, 20\dots, 2000, 2006, 2011$ (или ни одной). Обсуждение

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

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


Награды

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


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

====================================

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

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