Городская олимпиада по математике среди физ-мат школ Алматы, 2009 год

В стране есть $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: