===== ММ161 =====

** Конкурсная задача ММ161 (РК-1) ** (3 балла)

//По мотивам задачи ММ132 (и ряда других)//

Граф G=<V,E> задан на множестве V = {1, 2, ..., 1000000000000} по правилу: {a,b} ∈ E тогда и только тогда, когда сумма чисел a и b равна некоторой четной натуральной степени их разности.
Найти число связных компонент G и диаметр наибольшей компоненты.                                                     

**Решение**

Приведу {{:marathon:mm161.pdf|решение}} Дмитрия Пашуткина 

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

Соседние вершины цепочки длиной 1414212 - это, конечно же, последовательные треугольные числа.

Подсчет числа связных компонент можно осуществить чуть проще. Для этого нет нужды находить число вершин в каждой компоненте. Достаточно убедиться отсутствии циклов и вычесть из числа вершин число ребер.

Задача представлялась мне предельно легкой. Не зря же ее цена всего 3 балла (меньше в Марафоне не бывает). При этом неожиданно большим оказалось количество ошибок в присланных ответах. Полагаю, участники Марафона просто еще не обрели должную концентрацию после лета. 
Потому и ошибались: то, забывая о четности показателя степени; то, путаясь в арифметике; то, полагая диаметр цепи равным числу вершин...
Поскольку цена задачи изначально невелика, самые незначительные ошибки остались безнаказанными.


**Награды**

за правильное решение задачи ММ161 Сергей Половинкин, Олег Полубасов, Евгений Гужавин и Дмитрий Пашуткин получают по 3 призовых балла. Алексей Волошин, Виктор Филимоненков, Николай Дерюгин и Анатолий Казмерчук получают по 2 призовых балла.

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