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


Содержание

ММ161

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

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

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

Решение

Приведу решение Дмитрия Пашуткина

Обсуждение

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

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

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

Награды

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

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


 

 


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

marathon/problem_161.txt · Последние изменения: 2012/11/19 09:21 (внешнее изменение)
Powered by DokuWiki  ·  УКЦ ВГПУ 2006