Skip to main content
OlympiadHQ

Browse · MathNet

Print

Bulgaria

Bulgaria counting and probability

Problem

Every two of towns in a country are connected by one way or two way road. It is known that for every towns there exists round trip passing through each of these towns exactly once. Find the maximal possible number of one way roads.
Solution
Suppose there exists a town with one way roads all of which are pointing in one and the same direction from . Town with all end points of one way roads form a group of towns that violates the condition of the problem. We conclude that for any town there exist at most one way roads in the town and at most roads out of the town. Therefore the one way roads are at most .

We show now that when , it is possible to have all roads to be one way roads and when then the maximal number of one way roads equals .

Let and consider the towns to be vertexes of a regular -gon. For every town let one way roads out of point to the next towns clockwise. Since such allocation is possible and every two towns are connected with one way road. Consider a group of towns and order them clockwise. Between any two neighbors and there exists one way road from to . Therefore the desired round trip exists.

When , it suffices to choose arbitrary towns from the above construction.

When we proceed by similar manner. Connect every town with one way road from with the next towns. Let all remaining roads be two way roads.

Take arbitrary towns. Consider a group of towns and order them clockwise. Between any two neighbors and there exists one way road from to . Therefore the desired round trip exists.

Answer. When all roads could be one way and when there exist at most one way roads.
Final answer
If n ≤ 2k − 3, the maximum is n(n − 1)/2. If n > 2k − 3, the maximum is n(k − 2).

Techniques

Coloring schemes, extremal argumentsOther