Математикадан Алматы қаласының олимпиадасы, 2008 жыл

Мемлекетте $n$ қала бар және кейбір екі қалалардың арасында жолдар бар. Кез келген қаладан шыққан жолаушы, жолдармен басқа қалаларға барса және шыққан қалаға қайтып оралса, осы сапарда қалалардың саны (шыққан қаланы қосса есептегенде) әрқашан жұп саны болып табылады. Осы мемлекеттің жолдар санының ең көбісін анықтаңыз.

Комментарий/решение

Формулировка, на мой взгляд, несколько некорректная. По идее нужно добавить, что при передвижении из города в город мы не должны посещать никакой из городов (кроме исходного) дважды, то есть путь должен быть простым. Иначе если есть хотя бы три города А,В,С, такие что В соединен с А и С, то можно выехать из А в В, затем в С, а потом вернуться в В и потом в А, в итоге будет посещено только 3 города. Таким образом задача становится тривиальной: количество дорог равно [n/2], так как из любого города не может идти больше одной дороги.

Если же сделать предположение, о котором я написал выше, то из условия задачи следует, что граф дорог страны должен быть двудольным. В нашем случае это означает, что множество городов можно разбить на два непересекающихся подмножества таким образом, что из города каждого из подмножеств дороги ведут только в города другого подмножества.

Очевидно, что при заданном разбиении городов на два подмножества наибольшее количество дорог будет если любые два города из разных подмножеств соединены дорогой (в противном случае мы можем достроить недостающую дорогу, количество дорог, очевидно, увеличится). Если одно подмножество городов содержит m городов, то второе --- n-m. Так как каждый город соединен с каждым из другого подмножества, общее количество дорог будет m(n-m)=-n2+nm. Таким образом, на надо найти такое разбиение городов на подмножества (то есть найти, сколько городов должно быть в каждом из подмножеств), чтобы знаение выражения -m^2+mn было наибольшим. Так как это выражение -- квадратный трехчлен, графиком которого является парабола с ветвями вниз, необходимо взять вершину этой параболы, то есть m=n\2, если это возможно (т. е. если n - четное) и наиболее близкое к этому числу значение, есил n\2 не целое. Таким образом m=[n\2], а значит общее число дорог равно -[n/2]^2+[n/2]n. После очевидных преобразований ответ можно привести к виду [n^2/4]

ошибочка получилась у меня: не m(n-m)=-n2+nm, а m(n-m)=-m^2+nm: