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


Содержание

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


 

 


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

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